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

目录

前言

一、移除链表元素

二、反转链表

三、链表的中间结点

四、合并两个有序链表

总结

---

前言

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

---

一、移除链表元素

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

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

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

        解题步骤如下：

1. 初始化两个指针：newHead和newTail都初始化为NULL，分别用于记录新链表的头部和尾部。

2. 遍历原链表：使用pcur指针遍历原链表的所有节点。

3. 筛选节点：对于每个节点，如果值不等于val，则将其插入到新链表的尾部。

4. 尾插操作：

        如果新链表为空：将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节点的值是否为valif (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步// 循环条件：快指针和快指针的下一个节点都不为NULLwhile(fast != NULL && fast->next != NULL){slow = slow->next;        // 慢指针移动1步fast = fast->next->next;  // 快指针移动2步}return slow;  // 慢指针指向中间节点
}

四、合并两个有序链表

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

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

        画图分析：

        解题步骤如下：

1. 处理空链表情况：如果其中一个链表为空，直接返回另一个链表

2. 创建虚拟头节点：使用newHead和newTail来构建新链表

3. 比较并合并：同时遍历两个链表，每次选择较小的节点插入新链表

4. 处理剩余节点：将未遍历完的链表直接连接到新链表尾部

5. 清理并返回：释放虚拟头节点，返回真正的头节点

        完整代码如下：

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;     // 返回合并后的头节点
}

---

总结

        以上就是本期博客的全部内容啦！本期我们先介绍这四道题，下期博客将继续介绍剩余的四道题，请大家多多关注哦！