数据结构与算法：单链表综合练习（删除节点、反转、找中间节点）

数据结构与算法：单链表综合练习

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

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

1.1 题目

题目来源： LeetCode 删除链表中等于给定值 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;
}

二、反转链表

2.1 题目

题目来源： LeetCode 反转链表

2.2 算法原理

使用三指针法逐步反转链表结构。

• n1 指向当前节点的前驱（初始为 NULL）
• n2 指向当前节点（初始为 head）
• n3 指向当前节点的后继（用于暂存，防止断链）

注 1：n3 会最先指向 NULL 所以要特判； 注 2：链表可能为空，为空直接返回；

2.3 代码

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

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

三、链表中间节点

3.1 题目

题目来源： LeetCode 链表中间节点

3.2 算法原理

核心思想：快慢指针（fast 速度是 slow 的两倍）。

当 fast 到达末尾时，slow 刚好在中间。

注意：不能 fast->next && fast，当遇到偶数链表会造成对空指针解引用。

3.3 代码

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

struct ListNode* middleNode(struct ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}