单链表综合练习：删除指定节点、反转与查找中间节点

单链表核心操作实战

链表是 C 语言指针操作的经典场景，也是数据结构面试中的高频考点。掌握链表的增删改查，尤其是涉及指针指向变更的逻辑，对理解内存管理至关重要。下面我们通过三个典型题目，拆解链表操作的核心思路。

一、删除链表中等于给定值 val 的所有节点

思路解析

这道题的关键在于如何处理头结点可能也需要被删除的情况。如果直接遍历原链表修改 next 指针，需要额外处理 head 为空或 head 本身即为目标值的情况。

这里采用一种更稳健的方法：构建一个新链表。遍历原链表，将不等于 val 的节点依次尾插到新链表中。这样既避免了复杂的空指针判断，逻辑也相对清晰。需要注意的是，新链表构建完成后，务必将尾节点的 next 置为 NULL，防止形成环。

参考实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;

struct ListNode* removeElements(struct ListNode* head, int val) {
    ListNode* newhead = NULL;
    ListNode* newtail = NULL;
    ListNode* pcur = head;

    while (pcur) {
        if (pcur->val != val) {
            if (newhead == NULL) {
                // 链表为空，初始化头尾指针
                newhead = newtail = pcur;
            } else {
                // 尾插法连接节点
                newtail->next = pcur;
                newtail = pcur;
            }
        }
        pcur = pcur->next;
    }

    // 重要：断开新链表尾部，避免野指针
    if (newtail) newtail->next = NULL;
    return newhead;
}

二、反转链表

思路解析

反转链表是考察指针操作熟练度的经典题。核心思想是改变每个节点的 next 指向，使其指向前一个节点。为了在断链的同时不丢失后续节点，我们需要三个指针：

1. prev（前驱）：初始化为 NULL，最终将成为新的头结点。
2. curr（当前）：初始化为 head，负责遍历和修改指向。
3. next（后继）：暂存 curr 的下一个节点，防止断链后无法继续遍历。

循环中，先将 curr 的 next 指向 prev，然后三者同步向后移动。注意处理空链表的情况，直接返回即可。

参考实现

struct ListNode* reverseList(struct ListNode* head) {
    // 边界检查：空链表直接返回
    if (head == NULL) return head;

    ListNode* n1 = NULL;      // 前驱节点
    ListNode* n2 = head;      // 当前节点
    ListNode* n3 = head->next; // 后继节点

    while (n2) {
        n2->next = n1;        // 反转指针方向
        n1 = n2;              // 前驱后移
        n2 = n3;              // 当前后移
        if (n3) n3 = n3->next; // 后继后移
    }
    return n1; // n1 即为新的头结点
}

三、链表中间节点

思路解析

寻找中间节点最优雅的方案是使用快慢指针。定义两个指针 slow 和 fast，初始都指向头结点。slow 每次走一步，fast 每次走两步。当 fast 到达链表末尾时，slow 恰好位于中间位置。

这里有一个细节需要注意：循环条件应写为 while(fast && fast->next)。如果只写 fast，在偶数长度链表中，fast 可能会走到 NULL 后再访问 fast->next 导致空指针解引用异常。此外，对于偶数个节点，通常返回第二个中间节点，该逻辑天然符合上述循环条件。

参考实现

struct ListNode* middleNode(struct ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    // 确保 fast 和 fast->next 均有效
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

---

以上三个题目涵盖了链表操作中'删除'、'反转'和'遍历定位'的基础模式。在实际开发中，遇到类似结构问题时，不妨先画图理清指针关系，再动手编码，能有效减少空指针错误。建议结合图示反复调试代码，加深理解。