《链表面试基础看点：这里不止“快慢指针”的完美实现，更懂“哨兵节点”的巧妙运用》

🔥@晨非辰Tong：个人主页 

👀专栏：《C语言》、《数据结构与算法》、《数据结构与算法刷题集》

💪学习阶段：C语言、数据结构与算法初学者

⏳“人理解迭代，神理解递归。”

引言：链表刷题进行时。寻找中间结点，看似简单，但你的解法是否考虑了所有边界情况？本文手把手带你用“快慢指针”写出完美解，以及“哨兵节点”对合并链表的简化实现。

目录

1.  876. 链表的中间结点 - 力扣（LeetCode）（快慢指针）

2.  21. 合并两个有序链表 - 力扣（LeetCode）

1.  876. 链表的中间结点 - 力扣（LeetCode）（快慢指针）

方法一：遍历链表计算总大小，算出mid，将首节点指针向后mid个节点。（容易想到）

方法二：使用快、慢指针，慢指针动一步、快指针动两步。

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head) { //创建快慢指针 ListNode* fast, *slow; //首先都指向头节点 fast = head; slow = head; //循环条件将两种情况都包含 while(fast != NULL && fast->next != NULL)//条件换顺序？ { //慢指针移动一节点 slow = slow->next; //快指针移动两个节点 fast = fast->next->next; } //返回slow return slow; }

--为什么慢指针移动一个节点，快指针移动两个节点，是固定的吗？
        ：很好理解，因为是找 mid ，以慢指针所在节点为关注，那么快指针移动的是慢指针的两倍—>当快指针移动到尾节点或空，那么慢指针就指向 mid 。

--循环条件为什么不是或的关系？
        ：在循环体中实现的的是奇数或偶数个节点链表的寻找，那么只要两个条件只有都满足才能进行。

    

--上面提到，循环条件可以换位置吗？

        ：对偶数个节点进行分析

2.  21. 合并两个有序链表 - 力扣（LeetCode）（“哨兵”位）

• 方法一：创建新链表，比较大小，小的尾插新链表

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { //判断两个链表是否是空链表 if(list1 == NULL) { return list2;//直接返回list2 } if(list2 ==NULL) { return list1;//直接返回list1 } //创建空链表：空的首节点 ListNode* newhead, *newtail; newhead = newtail = NULL; //两个指向指针 ListNode* l1 = list1; ListNode* l2 = list2; //遍历原链表 //先将相同长度内的节点进行比较 while(l1 != NULL && l2 != NULL) { if(l1->val < l2->val) { //l1尾插 //第一回尾插，链表为空 if(newhead == NULL) { newhead = newtail = l1;//为头、为尾 } //后续尾插 else { newtail->next = l1; newtail = newtail->next; //尾后移 } l1 = l1->next;//链表1后移 } else { //l2尾插 //第一回尾插，链表为空 if(newhead == NULL) { newhead = newtail = l2;//为头、为尾 } //后续尾插 else { newtail->next = l2; newtail = newtail->next; //尾后移 } l2 = l2->next; } //跳出循环，代表有链表走到了空 if(l1) { newtail->next = l1; } if(l2) { newtail->next = l2; } } return newhead; }

--前面进行的单独判断为空：防止后续解引用空指针。

--最后面的是判断哪个链表走到了空，直接将另一个链表链接到尾节点。

• 改良：减少代码冗余

--发现上面的两串代码重复性很高，为什么？？

        ：初始时，设置的头节点、尾节点为空，导致尾插都要判断是否为空——>创建非空链表？——>可以！

typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { //判断两个链表是否是空链表 if(list1 == NULL) { return list2;//直接返回list2 } if(list2 ==NULL) { return list1;//直接返回list1 } //创建非空链表：申请一份节点的空间 ListNode* newhead, *newtail; newhead = newtail = (ListNode*)malloc(sizeof(ListNode)); //两个指向指针 ListNode* l1 = list1; ListNode* l2 = list2; //遍历原链表 //先将相同长度内的节点进行比较 while(l1 != NULL && l2 != NULL) { if(l1->val < l2->val) { //l1尾插 newtail->next = l1; newtail = newtail->next; //尾后移 l1 = l1->next;//链表1后移 } else { //l2尾插 newtail->next = l2; newtail = newtail->next; //尾后移 l2 = l2->next; } //跳出循环，代表有链表走到了空 if(l1) { newtail->next = l1; } if(l2) { newtail->next = l2; } } //手动申请的空间自己要释放 //释放前，保存节点 ListNode* retnewhead = newhead->next; free(newhead); newhead = NULL; return retnewhead; }

改良：申请一份节点大小的空间，让头、尾节点直接指向这个空间（“哨兵节点”），就不需要后面的判断是否为空链表了。



--不是遇到重复代码，可以封装函数吗？

        ：没错，但只是代码的呈现形式改变了而已，实际的逻辑没有变。

--后面虽然结束后，会自动释放，但是还要保持良好的习惯。

--后面新创建的 retnewhead 指向的是 newhead 的下一个节点（不要倒在小错误上！）。

回顾：

《一招吃透链表操作：三指针反转法，面试遇到链表题再也不慌！》

《算法面试“必杀技”：双指针法高效解决数组原地操作》

结语：掌握“快慢指针”这一基础工具，就能优雅地解决“中间结点”问题，而“哨兵节点”的应用更为我们后续攻克“双向链表”等复杂题目打下了坚实基础下一题刷题之道，在于积跬步以致千里。，再见~~