链表面试基础：快慢指针与哨兵节点的实战应用

链表是数据结构面试中的高频考点。掌握核心技巧往往比死记硬背代码更重要，本文通过两个经典题目解析关键思路。

876. 链表的中间结点

寻找中间结点看似简单，但边界情况容易出错。常规思路是先遍历一次统计长度，算出 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 = head;
    ListNode* slow = head;
    
    // 循环条件需同时满足：fast 不为空且 fast->next 不为空
    // 这样能兼容奇数和偶数长度的链表
    while(fast != NULL && fast->next != NULL) {
        slow = slow->next;       // 慢指针移动一节点
        fast = fast->next->next; // 快指针移动两节点
    }
    return slow;
}

为什么这么写？ 找中点时，关注的是慢指针的位置。快指针速度是慢指针的两倍，当它走到尾或空时，慢指针刚好走了半程。循环条件用'且'而非'或'，是因为只有当 fast 和 next 都存在时，才能安全执行 fast->next->next，避免空指针解引用。

21. 合并两个有序链表

合并两个有序链表时，直接比较大小并尾插新节点是直观做法，但需要处理大量空指针判断，代码冗余较多。

引入'哨兵节点'可以简化逻辑。哨兵节点是一个不存储有效数据的临时头节点，它的 next 指针最终指向真正的头节点。使用哨兵后，无需在循环内判断是否为第一次插入，统一进行尾插操作即可。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 处理空链表边界
    if(list1 == NULL) return list2;
    if(list2 == NULL) return list1;
    
    // 申请哨兵节点空间
    ListNode* newhead = (ListNode*)malloc(sizeof(ListNode));
    ListNode* newtail = newhead;
    
    ListNode* l1 = list1;
    ListNode* l2 = list2;
    
    // 双指针遍历比较
    while(l1 != NULL && l2 != NULL) {
        if(l1->val < l2->val) {
            newtail->next = l1;
            newtail = newtail->next;
            l1 = l1->next;
        } else {
            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);
    return retnewhead;
}

关键点说明：

1. 哨兵的作用：消除了对 newhead 是否为空的判断，统一了插入逻辑。
2. 内存管理：哨兵节点是动态申请的，最后必须释放，防止内存泄漏。
3. 返回值：返回的是 newhead->next，因为哨兵本身不是数据节点。

掌握这两个技巧，不仅能解决当前问题，也为后续攻克双向链表、复杂指针操作打下坚实基础。刷题重在理解背后的设计思想，积跬步以致千里。