代码随想录算法训练营 Day04 | 链表 part02
24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
class Solution { public: // 方法：虚拟头节点 + 迭代 ListNode* swapPairs(ListNode* head) { if(head == NULL) return head; // 1. 创建虚拟头节点，统一处理头节点交换 ListNode *dummy = new ListNode(0); dummy->next = head; // pre 指针：指向【待交换两个节点的前一个节点】 ListNode *pre = dummy; ListNode *cur, *next; // 定义两个待交换节点 // 循环条件：后面至少有两个节点才能交换 while(pre->next && pre->next->next) { // 定位三个关键节点 cur = pre->next; // 第一个节点 next = cur->next; // 第二个节点 // 核心三步交换 cur->next = next->next; // 1. 第一个节点 指向 第三个节点 next->next = cur; // 2. 第二个节点 指向 第一个节点 pre->next = next; // 3. 前驱节点 指向 新的第一个节点 // pre 移动到下一组的前驱位置（cur 已经变成后节点） pre = cur; } return dummy->next; } };总结
- 用了 dummy 虚拟头节点不用单独处理链表头部交换，所有组逻辑统一。
- 循环条件严谨
pre->next && pre->next->next保证剩下不足两个节点就停止，不会空指针报错。 - 空间复杂度 O (1)，只操作指针，不新建节点。
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第
n个结点，并且返回链表的头结点。
class Solution { public: // 算法：快慢指针（快指针先走 N 步，再一起走） ListNode* removeNthFromEnd(ListNode* head, int n) { // 快指针 p ListNode *p = head; // 快指针先走 n 步 while(n--) p = p->next; // 如果快指针走到空 → 要删的是【头节点】 if(!p) head = head->next; else { // 慢指针 cur，pre 是前驱 ListNode *pre = NULL; ListNode *cur = head; // 一起走，直到快指针到末尾 while(p){ p = p->next; pre = cur; cur = cur->next; } // 前驱跳过 cur，完成删除 pre->next = cur->next; delete cur; } return head; } };总结
1. 倒数第 N 个节点 = 正数第 len - N + 1 个节点
2. 快慢指针三步:
- 快指针先走 n 步
- 快慢一起走，直到快指针到末尾
- 此时慢指针正好指向倒数第 N 个节点
面试题 02.07. 链表相交
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回null。
class Solution { public: // 方法：先求长度 → 对齐起点 → 同时遍历找交点 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *p1 = headA; ListNode *p2 = headB; int len1 = 0, len2 = 0; // 1. 计算链表A的长度 len1 while(p1){ len1++; p1 = p1->next; } // 2. 计算链表B的长度 len2 while(p2){ len2++; p2 = p2->next; } // 重置指针回到头部 p1 = headA; p2 = headB; // 3. 计算长度差，让长链表先走 dif 步，实现对齐 int dif = len1 - len2; if(dif >= 0){ // A更长，A先走 dif 步 while(dif--) p1 = p1->next; } else { // B更长，B先走 dif 步 dif = -dif; while(dif--) p2 = p2->next; } // 4. 两个指针【同时同速】向后走，相等就是交点 while(p1 && p2){ if(p1 == p2) return p1; // 找到相交节点 p1 = p1->next; p2 = p2->next; } // 遍历完没找到 → 不相交 return NULL; } };总结
1. 先对齐，再同步走，相遇就是交点
- 算长度：算出两个链表的长度差
- 对齐：长链表先走几步，让两个指针在同一水平线
- 找交点：两个指针一起走，地址相同就是交点
2. 为什么判断p1 == p2而不是值相等？
- 相交的定义是：节点是同一个（内存地址一样）
- 不是值相等就算相交！
142. 环形链表 II
给定一个链表的头节点
head，返回链表开始入环的第一个节点。如果链表无环，则返回null。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
class Solution { public: // 算法：快慢指针 + 双指针找入口（Floyd 判圈算法） ListNode *detectCycle(ListNode *head) { // 快慢指针都从头节点出发 ListNode *slow = head; ListNode *fast = head; // 第一步：快慢指针往前走，判断是否有环 // 快指针走两步，慢指针走一步 while(fast && fast->next) { slow = slow->next; // 慢指针走 1 步 fast = fast->next->next; // 快指针走 2 步 // 快慢指针相遇 → 说明有环 if(slow == fast) { // 第二步：一个指针从头走，一个从相遇点走 // 速度相同，再次相遇点就是【环入口】 ListNode *pre = head; while(pre != fast) { pre = pre->next; fast = fast->next; } // 找到环入口，返回 return pre; } } // 循环退出 → 无环，返回 NULL return NULL; } };总结
1. 两步走
- 快 2 慢 1，相遇证明有环；
- 从链表头部和相遇点各出发一个指针，每次都走 1 步，最终一定会在环的入口相遇。
2. 代码关键细节
- 循环条件
while(fast && fast->next)快指针走两步，必须保证fast和fast->next都不为空，否则会报空指针错误。 - 相遇后才找入口只有快慢指针相遇，才能确定链表有环，再执行入口查找逻辑。
- 复杂度时间 O(n)，空间 O(1)，最优解法。
链表章节总结
一、常用方法
1.虚拟头节点 dummy
- 解决：头节点需要删除 / 插入的麻烦
- 让所有节点操作统一
- 用到的题：移除元素、两两交换、设计链表
2.双指针
- 快慢指针：环形链表、删除倒数第 N 个
- 前后指针：反转链表、删除节点
- 对齐指针：相交链表
二、核心思路
1. 移除链表元素
dummy + 双指针，找到就删，pre 接上 cur 的下一个
2. 设计链表
dummy 维护头尾，size 记录长度，增删查改统一操作
3. 反转链表
保存 next → 反转指向 → 双指针后移
4. 两两交换节点
dummy 定位前驱，三步交换指针，pre 跳到下一组
5. 删除倒数第 N 个
快指针先走 N 步，再一起走，慢指针指向要删节点
6. 相交链表
算长度 → 长链表先走 → 对齐后一起走，相遇即交点
7. 环形链表 II（最难）
快 2 慢 1 相遇证明有环头节点 + 相遇点同步走，相遇即环入口
三、模板
1. 反转链表模板
ListNode* reverseList(ListNode* head) { ListNode *pre = NULL, *cur = head; while(cur) { ListNode* tmp = cur->next; cur->next = pre; pre = cur; cur = tmp; } return pre; }2. 双指针删除 / 遍历模板
dummy->next = head; pre = dummy, cur = head; while(cur) { if(需要删除) { pre->next = cur->next; delete cur; cur = pre->next; } else { pre = cur; cur = cur->next; } }3. 快慢指针（环 / 倒数第 N 个）
slow = fast = head; while(fast && fast->next) { slow++; fast += 2; if(slow == fast) ... }