《每日一套题·提升你我能力》· 第五篇

大家好，我是安然无虞。

文章目录

• 每篇前言
• 
  

  一、选择填空题

• • 知识点补充
  • 1.题目一：考察性质
  • 2.题目二：考察性质
  • 3.题目三：考察性质
  • • 方法1
    • 方法2
  • 4.题目四：考察性质
• 
  

  二、编程设计题

• • 面试题：反转链表
  • • 解题思路1：翻指针方向
    • 解题思路2：头插法
  • 面试题：链表的中间节点
  • • • 解题思路
  • 面试题：回文链表
  • • 解题思路
• 
  

  三、遇见安然遇见你，不负代码不负卿。
  

  
  

每篇前言

---

博客主页：安然无虞

作者认证：2021年博客新星Top2

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请铁汁批评斧正。

火爆专栏：蓝桥杯基础算法剖析
欢迎加入：比特社区

种一棵树最好的时间是十年前，其次是现在。

各位，共勉。

---

一、选择填空题 知识点补充

I.满二叉树和完全二叉树：

• 一个二叉树， 如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。
  

  
  

  也就是说， 如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树；

• 对于深度为K且有 n 个结点的二叉树， 当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树 。
  

  
  

  要注意的是满二叉树是一种特殊的完全二叉树。
  

  
  

  （可能这样叙述并不是很清楚，没关系，请看下面）

看过来：
II.二叉树性质：

• 若规定根节点的层数是1，则一颗非空二叉树的第i层最多有2^(i-1) 个节点；
• 如规定根节点的层数是1，则深度为h的二叉树的最大节点数是2^h - 1，对，属于满二叉树；
• 对于任何一棵二叉树来说，如果度为0的叶节点个数是N0，度为2的节点个数是N2，那么总有N0 = N2 + 1;
• 若规定根节点的层数是1，具有n个节点的满二叉树的深度是h = log(N+1)。
  

  
  

1.题目一：考察性质

1.某二叉树共有399个节点，其中199个是度为2的节点，则该二叉树的叶子节点是：___ 个

本题主要考查性质三，X0 = X2 + 1，所以X0 = 200，即叶子结点个数为200个，这道题目知道性质3就很简单了。

---

2.题目二：考察性质

2.在具有2n 个节点的完全二叉树中，叶子结点个数为：___ 个。

需要注意的是，对于完全二叉树来说，度为1的结点个数只可能有0个或者1个。

---

3.题目三：考察性质

一颗完全二叉树的节点个数为531个，那么这棵树的高度为()
A:11
B:10
C:8
D:12

方法1

方法2

代入之后很明显，答案选择B

---

4.题目四：考察性质

一个具有767个节点的完全二叉树，其叶子结点个数为()
A:383
B:384
C:385
D:386
这道题跟第二题很相似，所以能看出什么，性质很重要，需要记住哦。

二、编程设计题 面试题：反转链表

原题链接：反转链表
题目描述：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例：

解题思路1：翻指针方向

不过直接翻指针方向这个方法定义两个指针是翻不动的，需要定义三个指针，可能看下图很难理解，但是要结合代码去理解，最好自己能画一遍，尝试自己写一遍代码。

初始代码：

struct ListNode* reverseList(struct ListNode* head)
{
   //判断特殊情况
   if(head == NULL)
       return NULL;
   struct ListNode* n1 = NULL, *n2 = head, *n3 = n2->next;
   while(n2)
   {
       n2->next = n1;
       n1 = n2;
       n2 = n3;
       //注意哦，当n3指向空指针时再执行n3 = n3->next;会导致空指针异常
       if(n3)
           n3 = n3->next;
   }
   return n1;
}

完整代码：
优化后的代码：

struct ListNode* reverseList(struct ListNode* head)
{
   struct ListNode* n1 = NULL, *n2 = head;
   while(n2)
   {
       struct ListNode* n3 = n2->next;
       n2->next = n1;
       n1 = n2;
       n2 = n3;
   } 
   return n1;
}

是不是变得很简单，这样写也无需判断特殊情况。

完整代码：

解题思路2：头插法

之所以需要多定义一个指针，是因为要保证能找到下一个。

代码执行:

struct ListNode* reverseList(struct ListNode* head)
{
   struct ListNode* newHead = NULL;
   struct ListNode* cur = head;
   while(cur)
   {
       //之所以将next定义在循环里是为了防止head为空时造成野指针
       struct ListNode* next = cur->next;
       cur->next = newHead;
       newHead = cur;
       cur = next;
   }
   return newHead;
}

完整代码：

面试题：链表的中间节点

原题链接：链表的中间节点
题目描述：
给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例：

解题思路

本题比较简单，直接利用快慢指针即可但是有两点需要注意，会在下面给出
代码执行：

struct ListNode* middleNode(struct ListNode* head)
{
   struct ListNode* slow = head, *fast = head;
   //注意循环条件：想的是结束条件，写的是继续条件
   while(fast && fast->next)
   {
       slow = slow->next;
       fast = fast->next->next;
   }
   return slow;
}

完整代码：
试想：为什么循环条件不能写成fast->next && fast？
因为如果节点个数是偶数个，那么fast会走到最后一个节点的next位置，也就是NULL，此时再判断循环条件fast->next时会导致野指针。

（可能这样叙述不好理解哦，没关系，动手画画图就很容易理解啦。

）

面试题：回文链表

原题链接：回文链表
题目描述：
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。

示例：
1->2->2->1
返回：true

解题思路

之所以讲解前面两题，实际上都是为这道题准备的，本题的解题步骤是：

• 找出链表的中间位置；
• 逆置后半段
• 最后从头依次比较即可

代码执行：

//回文链表
class PalindromeList {
public:
   //判断中间结点
   struct ListNode* middleNode(struct ListNode* A)
   {
       struct ListNode* slow = A, *fast = A;
       while(fast && fast->next)
       {
           slow = slow->next;
           fast = fast->next->next;
       }
     return slow;
 }
   //反转后半部分
   struct ListNode* reverseAfter(struct ListNode* mid)
   {
       struct ListNode* newHead = NULL, *cur = mid;
       while(cur)
       {
           struct ListNode* next = cur->next;
           cur->next = newHead;
           newHead = cur;
           cur = next;
       }
       return newHead;
   }
   bool chkPalindrome(ListNode* A) 
   {
       // write code here
       //先判断中间结点
       struct ListNode* mid = middleNode(A);
       //再反转后半部分
       struct ListNode* rHead = reverseAfter(mid);
       while(A && rHead)
       {
           if(A->val != rHead->val)
           {
               return false;
           }
           else
           {
               A = A->next;
               rHead = rHead->next;
           }
      }
       return true;
   }
};

完整代码：

三、遇见安然遇见你，不负代码不负卿。

码字不易，求个三连 抱拳了兄弟们。