大家好，我是安然无虞。

文章目录

• 每篇前言
• 一、选择填空题
• • 知识点补充
  • 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;   }};

完整代码：

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

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