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 节点和一步步操作，能够避免出错并提高效率。

环的问题总结：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/