程序员崩溃瞬间：这4道链表题不会，面试直接凉凉？速补！！

坚持用 清晰易懂的图解 + 多语言代码，让每道题变得简单！ 🌟
🚀呆头个人主页详情
🌱呆头个人Gitee代码仓库
📌 呆头详细专栏系列
座右铭： “不患无位，患所以立。”

👨‍💻 程序员崩溃瞬间：这4道链表题不会，面试直接凉凉？速补！！

• 前言
• 目录
• 1.移除链表元素
• • 方法思路
  • 代码实现
  • 代码解释
• 2.反转链表
• • 方法思路
  • 代码实现
  • 代码解释
• 3.查找链表中间结点
• • 方法思路
  • 代码实现
  • 代码解释
• 4.合并两个有序链表
• • 方法思路
  • 代码实现
  • 代码解释
  • • 为什么不需要循环就能连接所有剩余节点？

前言

🚀 你好，欢迎来到《编程闯关记》！
这里是算法与数据结构的实战基地，也是你从“暴力解法”到“最优解”的进化场。

🔍 专栏初衷：

• 用清晰的图解 + 多语言代码（Python/Java/C++/C），拆解每道题背后的逻辑。
• 不只讲“怎么做”，更讲“为什么”——从题目分析、边界条件到复杂度优化。
• 适合想夯实基础或突击面试的你，尤其针对LeetCode/牛客高频题！

💡 如何使用本专栏：
1️⃣ 先独立思考：尝试自己写出第一版代码（哪怕很烂）。
2️⃣ 对比解法：看看我的思路和你的差异，吸收优化技巧。
3️⃣ 举一反三：每篇末尾会附相似题目链接，趁热打铁。

📌 坚持打卡：
算法没有捷径，但正确的方法能让你少走弯路。每天15分钟，和我一起用代码雕刻思维！

（正文开始👇）

目录

1.移除链表元素

力扣链接直达<请点击

方法思路

这个C语言实现采用了创建新链表的方式来处理删除操作，主要步骤如下：

1. 初始化新链表：使用newHead和newTail指针来构建新链表
2. 遍历原链表：使用pCur指针遍历原链表
3. 节点筛选：
   • 如果节点值不等于目标值，将其加入新链表
   • 如果节点值等于目标值，释放该节点内存
4. 处理链表末尾：确保新链表的末尾指向NULL
5. 返回新链表头节点

代码实现

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* newHead = NULL; // 新链表的头 struct ListNode* newTail = NULL; // 新链表的尾 struct ListNode* pCur = head; // 遍历原链表的指针 while (pCur != NULL) { if (pCur->val != val) { // 如果当前节点不需要删除，加入新链表 if (newHead == NULL) { newHead = newTail = pCur; } else { newTail->next = pCur; newTail = newTail->next; } pCur = pCur->next; } else { // 如果当前节点需要删除，跳过并释放内存 struct ListNode* toDelete = pCur; pCur = pCur->next; free(toDelete); } } // 确保新链表的末尾指向NULL（防止原链表末尾有残留指针） if (newTail != NULL) { newTail->next = NULL; } return newHead;}

代码解释

1. 初始化指针：

   • newHead和newTail初始化为NULL，用于构建新链表
   • pCur初始化为原链表头节点，用于遍历

2. 链表遍历：

   • 使用while循环遍历整个链表
   • 对每个节点判断其值是否等于目标值

3. 节点处理：

   • 保留节点：当节点值不等于目标值时，将其加入新链表
     • 如果是第一个保留的节点，同时设置newHead和newTail
     • 否则追加到newTail后面
   • 删除节点：当节点值等于目标值时
     • 保存要删除的节点指针
     • 移动pCur到下一个节点
     • 释放当前节点内存

4. 链表收尾：

   • 确保新链表的最后一个节点的next指向NULL
   • 防止原链表末尾有不需要的指针

5. 返回结果：

   • 返回新链表的头节点指针

这种方法的时间复杂度是O(n)，空间复杂度是O(1)，是一种高效且内存安全的实现方式。

2.反转链表

力扣链接直达<请点击

方法思路

这段代码实现了链表的反转操作，采用迭代法进行反转。主要步骤如下：

1. 初始化指针：

   • prev：指向已经反转部分的链表头，初始为NULL
   • pnext：临时保存下一个节点的指针
   • pcur：当前正在处理的节点，初始为链表头

2. 迭代过程：

   • 保存当前节点的下一个节点（pnext = pcur->next）
   • 将当前节点的next指针指向前一个节点（完成反转）
   • 移动prev和pcur指针继续处理下一个节点

3. 终止条件：

   • 当pcur为NULL时，表示已处理完所有节点

代码实现

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedef struct ListNode ListNode;struct ListNode* reverseList(struct ListNode* head) { ListNode* prev = NULL; ListNode* pnext = NULL; ListNode* pcur = head; while(pcur != NULL) { pnext = pcur->next; // 保存下一个节点 pcur->next = prev; // 反转当前节点的指针 prev = pcur; // 前驱节点移动到当前节点 pcur = pnext; // 移动到下一个节点 } return prev; // 返回新的链表头}

代码解释

1. 指针初始化：

   • prev初始化为NULL，表示反转后的链表初始为空
   • pcur初始化为head，从链表头开始处理

2. 反转过程：

   • 每次迭代中，首先保存当前节点的下一个节点（pnext）
   • 然后将当前节点的next指针指向prev，完成反转
   • 最后移动prev和pcur指针继续处理后续节点

3. 返回值：

   • 循环结束时，prev指向原链表的最后一个节点，即反转后的新链表头
   • 因此返回prev作为反转后的链表头

3.查找链表中间结点

力扣链接直达<请点击

方法思路

这段代码实现了查找链表中间节点的功能，采用了快慢指针法（也称为\"龟兔赛跑\"算法）。主要步骤如下：

1. 边界条件处理：如果链表为空，直接返回NULL
2. 初始化指针：
   • fast快指针（每次移动两步）
   • slow慢指针（每次移动一步）
3. 遍历链表：
   • 快指针每次移动两步
   • 慢指针每次移动一步
4. 终止条件：
   • 当快指针到达链表末尾时，慢指针正好指向中间节点

代码实现

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedef struct ListNode ListNode;struct ListNode* middleNode(struct ListNode* head) { if(head == NULL) // 处理空链表情况 return NULL; else { ListNode* fast = head; // 快指针 ListNode* slow = head; // 慢指针 while(fast != NULL && fast->next != NULL) { fast = fast->next->next; // 快指针每次移动两步 slow = slow->next; // 慢指针每次移动一步 } return slow; // 返回中间节点 }}

代码解释

1. 边界检查：

   • 首先检查链表是否为空（head == NULL）
   • 如果是空链表，直接返回NULL

2. 快慢指针初始化：

   • 快指针fast和慢指针slow都初始化为链表头节点

3. 遍历过程：

   • 快指针每次移动两步（fast = fast->next->next）
   • 慢指针每次移动一步（slow = slow->next）
   • 循环继续的条件是快指针及其下一个节点都不为NULL

4. 返回值：

   • 当快指针到达链表末尾时，慢指针正好指向中间节点
   • 返回慢指针指向的节点

• 奇数长度链表：快指针到达最后一个节点时，慢指针正好在中间
• 例如：1→2→3→4→5，慢指针停在3
• 偶数长度链表：快指针超过末尾时，慢指针停在第二个中间节点
• 例如：1→2→3→4，慢指针停在3（题目通常要求这种结果）

4.合并两个有序链表

力扣链接直达<请点击

方法思路

这段代码实现了合并两个有序链表的功能，采用迭代方法进行合并。主要步骤如下：

1. 边界条件处理：
   • 如果其中一个链表为空，直接返回另一个链表
2. 初始化合并链表：
   • 确定合并后链表的头节点（两个链表头中较小的那个）
3. 迭代合并：
   • 比较两个链表当前节点的值
   • 将较小值的节点连接到合并链表
4. 处理剩余节点：
   • 将未遍历完的链表剩余部分连接到合并链表末尾

代码实现

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedef struct ListNode ListNode;struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { // 处理空链表的情况 if (list1 == NULL) return list2; if (list2 == NULL) return list1; ListNode* head = NULL; // 合并后链表的头节点 ListNode* tail = NULL; // 合并后链表的尾节点 // 确定头节点（取两个链表头中较小的） if (list1->val <= list2->val) { head = list1; list1 = list1->next; } else { head = list2; list2 = list2->next; } tail = head; // 合并剩余节点 while (list1 != NULL && list2 != NULL) { if (list1->val <= list2->val) { tail->next = list1; list1 = list1->next; } else { tail->next = list2; list2 = list2->next; } tail = tail->next; } // 连接剩余节点 if (list1 != NULL) { tail->next = list1; } else { tail->next = list2; } return head;}

代码解释

1. 边界检查：

   • 检查两个链表是否为空，若其中一个为空则直接返回另一个

2. 初始化合并链表：

   • 比较两个链表头节点的值，选择较小的作为合并后链表的头节点
   • 移动被选中链表的指针到下一个节点

3. 迭代合并过程：

   • 比较两个链表当前节点的值
   • 将较小值的节点连接到合并链表的尾部
   • 移动相应链表的指针和合并链表的尾指针

4. 处理剩余节点：

   • 当其中一个链表遍历完后，将另一个链表的剩余部分直接连接到合并链表末尾

5. 返回值：

   • 返回最初确定的合并链表头节点

你说得对，我需要更清楚地解释这段代码的工作原理。让我们深入分析这个\"连接剩余节点\"的操作：

为什么不需要循环就能连接所有剩余节点？

关键在于理解链表的特性。当 while 循环结束时（即 list1 == NULL || list2 == NULL），此时：

1. 链表节点已经是有序的：在之前的循环中，我们已经按顺序连接了所有较小的节点
2. 剩余节点本身就是有序的：因为输入链表本来就是有序的
3. 只需要一次连接：剩余未处理的节点已经按顺序连接在一起