> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/l6lian-biao.md).
# L6\_链表（快慢指针）
### 链表知识点总结 - 简洁版
**1. 链表反转 (Reverse)**
* **核心思想：** 改变节点指向方向。
* **方法一：迭代 (循环首位相接)**
* 使用三个指针 `prev`, `curr`, `next`。
* 每次迭代将 `curr.next` 指向 `prev`，然后依次移动指针。
```
图示：
原始: A -> B -> C -> None
反转后: None <- A <- B <- C
```
* **方法二：头插法**
* 建立新的头节点。
* 将原链表的每个节点依次插入到新头节点的后面。
* **注意：** 反转后，原链表的头节点成为尾节点，其 `next` 指针需要重新设置。
反转链表首尾呼应的代码：
```
def reverse_list(head):
prev = None
curr = head
while curr:
next_node = curr.next # Save the next node
curr.next = prev # Reverse the link
prev = curr # Move prev to the current node
curr = next_node # Move to the next node
return prev
```
**2. 快慢指针 (Fast & Slow Pointers)**
* **用途：**
* 找到链表中间节点（或中偏后节点）。
* 检测链表是否有环。
* 解决链表相交问题。
* **原理：**
* 快指针每次移动两步，慢指针每次移动一步。
```
图示 (找中间节点)：
A -> B -> C -> D -> E -> None
快指针： A -> C -> E -> None
慢指针： A -> B -> C
```
**3. 链表相交 (Intersection)**
* **判断方法：**
* **方法一：快慢指针 + 环检测**
* 将一个链表的尾节点连接到另一个链表的头节点，形成一个环。
* 使用快慢指针判断是否有环。如果存在环，则说明两个链表相交。
* **方法二：尾节点比较**
* 找到两个链表的尾节点，如果尾节点相同，则说明链表相交。
* 相交链表从相遇点开始有相同的尾节点。
```
图示 (尾节点比较)：
A -> B -> C ↘
D -> E -> None
X -> Y ↗
```
**4. 辅助技巧**
* **Dummy 节点：** 在链表头部添加一个 dummy 节点，方便处理边界情况。
* **一步步走：** 避免使用 `node.next.next`，先设置 `node.next`，再移动 `node`。
**必做题:**
* **Reverse Nodes in k-Group:** 将链表每 k 个节点进行翻转。需要熟练掌握链表反转技巧，并注意处理边界情况。
**总结：**
链表操作的关键在于理解节点指向的变化。通过掌握反转、快慢指针、相交判断等技巧，可以解决大部分链表相关问题。记住使用 `dummy` 节点和一步步操作，能够避免出错并提高效率。
\-------------------------------------------------2025-------------------------------------------------
### 链表指针操作防乱指南（反转/增删/K组处理）
### 一、通用防乱原则
1. **虚拟头节点（Dummy Node）**\
在头节点可能变化的场景（如删除头节点、K组反转）必须使用：
```
pythondummy = ListNode(-1, head) # 创建虚拟头
# 操作结束后返回 dummy.next
```
2. **三指针法则**\
涉及指针反转时，必须同时维护 `pre`、`cur`、`nxt` 三个指针：
```
pythonpre, cur = None, head
while cur:
nxt = cur.next # 先保存后路
cur.next = pre # 反转指针
pre = cur # 移动pre
cur = nxt # 移动cur
```
3. **子链表切割法**\
处理局部操作时，先切割出独立子链表，操作完再重新连接：
```
python# 示例：反转 [a, b) 区间的链表
def reverse(a, b):
pre, cur = None, a
while cur != b:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre # 返回反转后的头
```
### 二、高频场景操作模板
### 场景1：反转K个一组的链表
```
pythondef reverseKGroup(head, k):
dummy = ListNode(-1, head)
pre = dummy
while True:
# 检查剩余节点是否>=k
check = pre
for _ in range(k):
check = check.next
if not check:
return dummy.next
# 切割子链表并反转
start = pre.next
end = check
nxt_group = end.next
pre.next = reverse(start, nxt_group) # 连接前驱
start.next = nxt_group # 连接后继
pre = start # 移动pre到下一组前驱
```
### 场景2：删除倒数第N个节点
```
pythondef removeNthFromEnd(head, n):
dummy = ListNode(-1, head)
fast = slow = dummy
# 快指针先走n+1步
for _ in range(n+1):
fast = fast.next
# 同步移动找到前驱
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next # 删除节点
return dummy.next
```
### 场景3：在排序链表插入新节点
```
pythondef insertNode(head, val):
dummy = ListNode(-1, head)
cur = dummy
while cur.next and cur.next.val < val:
cur = cur.next
new_node = ListNode(val)
new_node.next = cur.next # 先连后路
cur.next = new_node # 再改前驱
return dummy.next
```
### 三、防错检查清单
1. **指针移动前必保存后路**\
反转/删除时先保存 `nxt = cur.next`
2. **连接顺序遵循「新→旧」原则**\
插入新节点时先 `new.next = old`，再修改前驱指针
3. **边界条件验证**\
操作前后检查：
* 头尾节点是否特殊处理
* 空链表/单节点链表情况
* K值大于链表长度时的处理
4. **可视化画图法**\
面试时在白板画出指针变化示意图（示例见下图）
```
text
原始链表：Dummy → A → B → C → D
↑pre ↑cur ↑nxt
反转后： Dummy ← A ← B C → D
↑pre ↑cur ↑nxt
```
掌握这些模式可覆盖90%链表题型，建议结合LeetCode 25、92、19等题强化训练。
####
环的问题总结：