数据结构（C语言篇）：（五）单链表算法题（上）

_OP_CHEN

发布于 2026-01-14 09:30:27

490

文章被收录于专栏：C++C++

前言

本期将给大家讲解有关单链表的一些算法题，相信在看完这些算法题之后，大家能够对单链表有更深刻的了解。现在就让我们开始吧！

一、移除链表元素

题目链接：203. 移除链表元素 - 力扣（LeetCode）

思路：创建新链表，将链表中不为val中的结点拿下来尾插。

我们可以画图来分析一下：

解题步骤如下：

初始化两个指针：newHead和newTail都初始化为NULL，分别用于记录新链表的头部和尾部。
遍历原链表：使用pcur指针遍历原链表的所有节点。
筛选节点：对于每个节点，如果值不等于val，则将其插入到新链表的尾部。
尾插操作：

如果新链表为空：将newHead和newTail都指向当前节点；

如果新链表非空：将当前节点链接到newTail后面，并更新newTail。

5. 返回结果：返回新链表的头节点newHead。

完整代码如下：

struct ListNode* removeElements(struct ListNode* head, int val) {
    //创建新链表
    ListNode* newHead, * newTail;
    newHead = newTail = NULL;

    ListNode* pcur = head;
    while (pcur)
    {
        //判断pcur节点的值是否为val
        if (pcur->val != val)
        {
            //尾插
            if (newHead == NULL)
            {
                //链表为空
                newHead = newTail = pcur;
            }
            else {
                //链表非空
                newTail->next = pcur;
                newTail = newTail->next;
            }
        }
        pcur = pcur->next;
    }
    return newHead;
}

我们可以再来看一下该段代码的执行流程：

假设原链表：1 → 2 → 6 → 3 → 4 → 5 → 6，我们要删除值为6的节点：

遍历过程： pcur=1 (≠6) → 插入新链表：newHead=1, newTail=1 pcur=2 (≠6) → 插入新链表：1 → 2, newTail=2 pcur=6 (==6) → 跳过 pcur=3 (≠6) → 插入新链表：1 → 2 → 3, newTail=3 pcur=4 (≠6) → 插入新链表：1 → 2 → 3 → 4, newTail=4 pcur=5 (≠6) → 插入新链表：1 → 2 → 3 → 4 → 5, newTail=5 pcur=6 (==6) → 跳过最终结果：1 → 2 → 3 → 4 → 5

二、反转链表

题目链接如下：206. 反转链表 - 力扣（LeetCode）

思路：创建三个指针，改变原指针的指向。

依旧先来画图分析：

解题步骤分析如下：

1. 初始化三个指针：

n1：指向已反转部分的头节点（初始为NULL）；

n2：指向当前要处理的节点（初始为head）；

n3：指向下一个要处理的节点（初始为n2->next）。

2. 迭代反转过程：

将当前节点n2的next指针指向前一个节点n1；

三个指针同时向前移动：n1移到n2，n2移到n3，n3移到下一个节点；

重复直到n2为NULL（遍历完所有节点）。

3. 返回结果：n1最终指向反转后的新头节点。

完整代码如下：

typedef struct ListNode ListNode;

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)  // 处理空链表情况
    {
        return head;
    }
    
    // 创建三个指针
    ListNode* n1, *n2, *n3;
    n1 = NULL;        // 已反转部分的头节点
    n2 = head;        // 当前要处理的节点
    n3 = n2->next;    // 下一个要处理的节点
    
    while (n2)        // 当还有节点需要处理时
    {
        n2->next = n1;  // 反转当前节点的指向
        
        // 三个指针向前移动
        n1 = n2;      // n1移动到当前已反转的头部
        n2 = n3;      // n2移动到下一个待处理节点
        
        if (n3)       // 防止对NULL指针解引用
            n3 = n3->next;
    }
    
    return n1;        // n1现在是新链表的头节点
}

代码执行流程分析：假设原链表为1 → 2 → 3 → 4 → NULL

初始状态： n1 = NULL, n2 = 1, n3 = 2 第1次循环： n2->next = n1 → 1 → NULL n1 = n2 → n1指向1 n2 = n3 → n2指向2 n3 = n3->next → n3指向3 当前：1 → NULL 第2次循环： n2->next = n1 → 2 → 1 → NULL n1 = n2 → n1指向2 n2 = n3 → n2指向3 n3 = n3->next → n3指向4 当前：2 → 1 → NULL 第3次循环： n2->next = n1 → 3 → 2 → 1 → NULL n1 = n2 → n1指向3 n2 = n3 → n2指向4 n3 = n3->next → n3指向NULL 当前：3 → 2 → 1 → NULL 第4次循环： n2->next = n1 → 4 → 3 → 2 → 1 → NULL n1 = n2 → n1指向4 n2 = n3 → n2指向NULL n3 = NULL (因为n3已经是NULL) 当前：4 → 3 → 2 → 1 → NULL 循环结束，返回n1(4)

三、链表的中间结点

题目链接：876. 链表的中间结点 - 力扣（LeetCode）

思路：快慢指针法，慢指针每次走一步，快指针每次走两步。

解题步骤分析如下：

1. 初始化两个指针：

slow（慢指针）：每次移动一步；

fast（快指针）：每次移动两步。

2. 同时移动指针：

当快指针fast还没有到达链表末尾时，继续移动；

慢指针slow每次移动1步，快指针fast每次移动2步。

3. 终止条件：

快指针fast为NULL（偶数个节点）；

或者快指针的next为NULL（奇数个节点）。

4. 返回结果：慢指针slow指向的就是中间节点。

完整代码如下所示：

typedef struct ListNode ListNode;

struct ListNode* middleNode(struct ListNode* head) {
    // 创建快慢指针
    ListNode* slow = head;  // 慢指针，每次移动1步
    ListNode* fast = head;  // 快指针，每次移动2步
    
    // 循环条件：快指针和快指针的下一个节点都不为NULL
    while(fast != NULL && fast->next != NULL)
    {
        slow = slow->next;        // 慢指针移动1步
        fast = fast->next->next;  // 快指针移动2步
    }
    
    return slow;  // 慢指针指向中间节点
}

四、合并两个有序链表

题目链接：21. 合并两个有序链表 - 力扣（LeetCode）

思路：创建新链表，遍历并比较原链表中结点的值，小的尾插到新链表中。

画图分析：

解题步骤如下：

处理空链表情况：如果其中一个链表为空，直接返回另一个链表
创建虚拟头节点：使用newHead和newTail来构建新链表
比较并合并：同时遍历两个链表，每次选择较小的节点插入新链表
处理剩余节点：将未遍历完的链表直接连接到新链表尾部
清理并返回：释放虚拟头节点，返回真正的头节点

完整代码如下：

typedef struct ListNode ListNode;

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 处理空链表情况
    if(list1 == NULL) return list2;
    if(list2 == NULL) return list1;
    
    // 创建虚拟头节点
    ListNode* newHead, *newTail;
    newHead = newTail = (ListNode*)malloc(sizeof(ListNode));
    newHead->next = NULL;  // 确保初始状态正确

    // 遍历原链表
    ListNode* l1 = list1;
    ListNode* l2 = list2;

    // 比较并合并
    while(l1 != NULL && l2 != NULL) {
        if(l1->val < l2->val) {
            newTail->next = l1;    // 将l1接入新链表
            newTail = newTail->next; // 移动尾指针
            l1 = l1->next;         // l1前进
        } else {
            newTail->next = l2;    // 将l2接入新链表
            newTail = newTail->next; // 移动尾指针
            l2 = l2->next;         // l2前进
        }
    }
    
    // 处理剩余节点
    if(l1) newTail->next = l1;  // l1还有剩余节点
    if(l2) newTail->next = l2;  // l2还有剩余节点
    
    // 清理虚拟头节点
    ListNode* retHead = newHead->next;  // 保存真正的头节点
    free(newHead);      // 释放虚拟头节点
    newHead = NULL;     // 避免野指针
    
    return retHead;     // 返回合并后的头节点
}