快慢指针

参考视频：https://www.bilibili.com/video/BV1KG4y1G7cu?spm_id_from=333.788.videopod.sections&vd_source=e43febe45084286ccca9027e2b3360b5

876. 链表的中间节点

876.链表的中间节点

解题思路（找中点）

使用快慢指针，快指针每次移动两步，慢指针每次移动一步。当快指针到达链表末尾时，慢指针恰好在中间位置。

代码实现：快慢指针找中点

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = slow = head
        while fast and fast.next:  # 分奇数偶数情况
            slow = slow.next
            fast = fast.next.next

        return slow

复杂度分析（找中点）

• 时间复杂度：$O(n)$，其中 $n$ 是链表的长度。快指针遍历整个链表一次。
• 空间复杂度：$O(1)$，只使用了两个指针变量。

141. 环形链表

141.环形链表

解题思路（环形检测）

使用快慢指针检测链表是否有环。快指针每次移动两步，慢指针每次移动一步。如果链表有环，快指针最终一定会追上慢指针；如果没有环，快指针会先到达链表末尾。

代码实现：链表是否成环

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:  # 快指针追上慢指针，说明有环
                return True

        return False

复杂度分析（成环检测）

• 时间复杂度：$O(n)$，其中 $n$ 是链表的长度。
  • 如果没有环，快指针会遍历整个链表
  • 如果有环，快指针最多在环中追赶慢指针一圈
• 空间复杂度：$O(1)$，只使用了两个指针变量。

142. 环形链表 II

142.环形链表 II

原理图解

快慢指针检测环形链表的工作原理：

关键点说明：

• a：从头节点到环入口的距离
• b：从环入口到快慢指针相遇点的距离
• c：从相遇点回到环入口的距离

数学推导

设定变量：

$$\text{环长} = b + c$$

$$\text{慢指针移动距离} = a + b$$

$$\text{快指针移动距离} = a + b + k(b + c)$$

其中 $k$ 表示快指针在环中多走的圈数。

因为快指针移动距离是慢指针的两倍，所以：

$$2(a + b) = a + b + k(b + c)$$

展开：

$$2a + 2b = a + b + b + c + (k - 1)(b + c)$$

化简：

$$a - c = (k - 1)(b + c)$$

因此：

$$a = c + (k - 1)(b + c)$$

关键结论：

当 $k = 1$ 时（快指针只比慢指针多走一圈），有：

$$a = c$$

这说明：从头节点到环入口的距离 = 从相遇点到环入口的距离

即使 $k > 1$，$a = c + (k-1)(b+c)$ 也表示从头节点走 $a$ 步到入口，等同于从相遇点走 $c$ 步再多绕 $(k-1)$ 圈回到入口。

算法策略

相遇后，让一个指针从头节点出发，另一个从相遇点出发，两者以相同速度（每次一步）移动，它们必然会在环入口处相遇。

参考代码

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast is slow:
                while slow is not head:
                    slow = slow.next
                    head = head.next
                return slow

        return None

时间空间分析

• 时间复杂度：$O(n)$，其中 $n$ 是链表的长度。
  • 第一阶段：快慢指针相遇，最多遍历链表一次
  • 第二阶段：两个指针从不同位置出发找入口，最多遍历链表一次
• 空间复杂度：$O(1)$，只使用了两个指针变量。

143. 重排链表

143.重排链表

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> None:
        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def reverseList(self, head: Optional[ListNode]) -> None:
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        mid = self.middleNode(head)
        head2 = self.reverseList(mid)

        while head2.next:
            nxt = head.next
            nxt2 = head2.next
            head2.next = nxt
            head.next = head2
            head = nxt
            head2 = nxt2

练习题

234. 回文链表

2130. 链表最大孪生和