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组处理）

一、通用防乱原则

虚拟头节点（Dummy Node） 在头节点可能变化的场景（如删除头节点、K组反转）必须使用：
```
pythondummy = ListNode(-1, head)  # 创建虚拟头
# 操作结束后返回 dummy.next
```

三指针法则 涉及指针反转时，必须同时维护 pre、cur、nxt 三个指针：

pythonpre, cur = None, head
while cur:
    nxt = cur.next  # 先保存后路
    cur.next = pre  # 反转指针
    pre = cur       # 移动pre
    cur = nxt       # 移动cur

子链表切割法 处理局部操作时，先切割出独立子链表，操作完再重新连接：

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

三、防错检查清单

指针移动前必保存后路 反转/删除时先保存 nxt = cur.next
连接顺序遵循「新→旧」原则 插入新节点时先 new.next = old，再修改前驱指针
边界条件验证 操作前后检查：
- 头尾节点是否特殊处理
- 空链表/单节点链表情况
- K值大于链表长度时的处理
可视化画图法 面试时在白板画出指针变化示意图（示例见下图）

text
原始链表：Dummy → A → B → C → D
           ↑pre   ↑cur ↑nxt

反转后： Dummy ← A ← B   C → D
                 ↑pre ↑cur ↑nxt

掌握这些模式可覆盖90%链表题型，建议结合LeetCode 25、92、19等题强化训练。

环的问题总结：https://blog.csdn.net/liuxialong/article/details/6555850

https://blog.csdn.net/liuxialong/article/details/6556096 https://blog.csdn.net/linchonghui888/article/details/79896127

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

Previous403. Frog Jump NextMedian of LinkedList

Last updated 1 month ago

Was this helpful?