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

前言

链表是 C 语言数据结构学习的核心考点，也是编程入门绕不开的经典题型。本文聚焦删除指定值节点、反转链表、查找中间节点三大高频链表题，从算法原理到代码实现逐拆解，用通俗易懂的逻辑和清晰的代码示例，帮你吃透链表操作的核心思路。掌握这些基础题型，不仅能夯实指针功底，更能为后续复杂数据结构学习筑牢根基。

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

题目

给定一个链表的头节点 head 和一个整数 val，请你删除链表中所有满足 node.val == val 的节点，并返回新的头节点。

算法原理

处理链表删除时，直接修改原链表往往需要特殊处理头节点的情况（比如头节点就是要删的值）。这里采用一种更稳健的思路：创建一个新链表，遍历原链表，把不等于 val 的节点依次尾插到新链表中。这样逻辑统一，不需要单独判断头节点是否被删除。

代码实现

/**
 * 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;
}

二、反转链表

题目

给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

算法原理

反转链表的核心在于改变节点的 next 指向。最直观的方法是使用三个指针：prev（前驱）、curr（当前）、next（后继）。

1. 初始时，prev 为 NULL，curr 为头节点。
2. 在循环中，先保存 curr->next 到 next，防止断链。
3. 将 curr->next 指向 prev，完成局部反转。
4. 移动 prev 和 curr 向后推进。
5. 当 curr 为空时，prev 即为新的头节点。

注意：如果链表为空，直接返回；遍历时务必先备份下一个节点，否则链表会断裂。

代码实现

struct ListNode* reverseList(struct ListNode* head) {
    // 链表为空直接返回
    if (head == NULL) return head;

    ListNode* prev = NULL;
    ListNode* curr = head;
    ListNode* next = head->next;

    while (curr) {
        curr->next = prev; // 反转指针方向
        prev = curr;       // 前驱后移
        curr = next;       // 当前后移
        if (next) {
            next = next->next; // 备份下一个节点
        }
    }
    return prev;
}

三、链表中间节点

题目

给定一个头节点为 head 的非空单链表，返回链表的中间节点。如果有两个中间节点，则返回第二个中间节点。

算法原理

这是经典的快慢指针问题。定义两个指针 slow 和 fast，都从头节点出发。

• slow 每次走一步。
• fast 每次走两步。

当 fast 到达链表末尾时，slow 恰好位于中间位置。对于偶数长度链表，fast 走到最后一个节点时停止，此时 slow 指向第二个中间节点，符合题目要求。

关键点：循环条件必须同时检查 fast 和 fast->next，避免访问空指针导致崩溃。

代码实现

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

    // 只要 fast 不为空且 fast 的下一个节点也不为空，就继续走
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

总结

本文解析了链表操作的三大高频题型：删除指定值节点、反转链表、查找中间节点。通过新链表尾插法实现删除操作，避免了复杂的边界判断；利用三指针迭代逐步反转链表，确保指针不丢失；采用快慢指针高效定位中间节点。代码示例清晰，附详细算法原理说明，帮助掌握链表核心操作逻辑。这些基础题型是提升指针运用能力和数据结构理解的关键，建议结合图示反复练习。