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

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

链表是 C 语言数据结构中的经典考点，也是指针操作的试金石。下面我们通过三个高频题型，拆解链表操作的核心逻辑。

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

1.1 题目描述

给定一个链表的头节点和一个整数值 val，要求删除所有值为 val 的节点并返回新的头节点。

1.2 算法思路

这里采用新建链表的方式来实现。遍历原链表，将不等于 val 的节点依次尾插到新链表中。这种方法逻辑直观，但会占用额外的空间。实际开发中若对空间敏感，也可考虑原地修改指针。

1.3 代码实现

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

注意在循环结束后，务必将新链表的尾部指针指向 NULL，否则可能残留旧链表的后续节点导致死循环。

二、反转链表

2.1 题目描述

给定单链表的头节点，反转链表并返回新的头节点。

2.2 算法思路

使用三指针法迭代完成。定义前驱指针 n1、当前指针 n2 和后继指针 n3。每次迭代将当前节点的 next 指向前驱，然后三者同步向后移动。

2.3 代码实现

typedef struct ListNode ListNode;

 ListNode*  {
    (head == )  head;
    ListNode* n1 = ;
    ListNode* n2 = head;
    ListNode* n3 = head->next;

    (n2) {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        (n3) n3 = n3->next;
    }
     n1;
}