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等题强化训练。

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

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

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