# 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组处理） <a href="#k" id="k"></a>

### 一、通用防乱原则

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/6556096><https://blog.csdn.net/linchonghui888/article/details/79896127>

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/l6lian-biao.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.