《链表面试基础看点：这里不止“快慢指针”的完美实现，更懂“哨兵节点”的巧妙运用》
🔥@晨非辰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 的下一个节点（不要倒在小错误上！）。
回顾：
《一招吃透链表操作：三指针反转法，面试遇到链表题再也不慌！》
《算法面试“必杀技”：双指针法高效解决数组原地操作》
结语：掌握“快慢指针”这一基础工具，就能优雅地解决“中间结点”问题，而“哨兵节点”的应用更为我们后续攻克“双向链表”等复杂题目打下了坚实基础下一题刷题之道，在于积跬步以致千里。，再见~~
