快慢指针简述
快慢指针经常用于链表 (linked list) 中环 (Cycle) 相关的问题.
快指针 (fast pointer) 和慢指针 (slow pointer) 都从链表的 head 出发.
slow pointer 每次移动一格, 而快指针每次移动两格.
如果快慢指针能相遇, 则证明链表中有环; 否则没有.
快慢指针的具体代码 (C++, Python, Java 版本) 可以参考这个链接.
LeetCode 中对应题目分别是:
141. Linked List Cycle https://leetcode.com/problems/linked-list-cycle/ 判断 linked list 中是否有环
142. Linked List Cycle II 找到环的起始节点 (entry node) 位置.
问题详解 -- 为什么如果有环, 则快慢指针必定会相遇?
我们假设以下变量:
\(L_1\): 起始节点 (head node) 到环起始节点 (entry node) 的距离.
\(C\): 环的长度.
假设我们的慢指针移动了 \(x\)步, 那么快指针就移动了 \(2x\)步.
那么必定有 \[(x-L_1)\% C= (2x-L_1) \% C \]\[(2x-x)\% C = 0\]\[x\%C=0\]
以上三个式子步步可逆, 由于 \(C\)是给定的 fixed value, 而 \(x\)每步都在上升, 因此必定有一个 \(x=wC(w\in {N})\)使得他们相遇. 并且有 \(L_1 \le x\)所以必有 \(x=\)\(\frac{L_1}{C}\)\(C\)为他们第一次相遇的地点. 因此有 \(x< L_1 + C\) where \(x=\)\(\frac{L_1}{C}\)\(C\)
这也就意味着他们相遇的地方一定是慢指针在环里的第一圈.
问题详解 -- 如何找到环的起始节点?
我们再增加一些变量:
\(L_2\): 环起始节点 (entry node) 到快慢指针相遇节点的距离.
\(k\): 慢指针和快指针相遇的时候, 慢指针走了的距离.
注意到, 因为快指针走了的距离总是慢指针走了的距离的两倍, 因此 \(2k\)是慢指针和快指针相遇的时候, 快指针走了的距离.
由慢指针可以得出 \[L_1+L_2=k\]由快指针可以得出, 其中 n 是快指针已经走过的圈数 \[L_1+nC+L_2 = 2k\]结合上述两个式子, 我们可以得出 \[nC=k\]
当慢指针在遇到了快指针之后, 慢指针又马上移动了, 那么慢指针需要移动 \(p\)步后就可以让慢指针就回到了环起始节点 (entry node). 与此同时, 在快慢指针相遇之后, 又有一个指针马上从原点出发, 那么它需要经过 \(q\) 步才能到达起始节点(entry node) 而且与慢指针相遇.
当慢指针和这个新指针相遇的时候, 有 \[(p-L_1)\%C=(q+L_2)\%C\]
由离散数学中的定理 https://en.wikipedia.org/wiki/Modular_arithmetic 可知 \[(p-q-L_1-L_2)\%C=0\]\[(p-q-nC)\%C=(p-q)\%C=0\]
不妨取 \(p=q\)即 \(p-q=0\Rightarrow (p-q)\%C=0\)
因此当他们同时回到环起始节点 (entry node) 的时候, 有慢指针第一次相遇后走过的距离 \(p\)和新指针走的距离 \(p=q\).
值得注意的是 \(L_2< C\), 因此, 他们第一相遇的时候必有 \(q<C-L_2\), 也就是说慢指针和新指针第一次相遇的时候, 他们必定都在环起始节点(entry node).
LeetCode 对应代码
判断 linked list 中是否有环(141. Linked List Cycle)
这个算法的时间复杂度是 O(n)
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, x):
- # self.val = x
- # self.next = None
- class Solution(object):
- def hasCycle(self, head):
- """
- :type head: ListNode
- :rtype: bool
- """
- if head is None:
- return False
- slow = head
- fast = head
- while(fast.next and fast.next.next):
- slow = slow.next
- fast = fast.next.next
- if slow == fast:
- return True
- return False
- 找到环的起始节点 (entry node) 位置(142. Linked List Cycle II)
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, x):
- # self.val = x
- # self.next = None
- class Solution(object):
- def detectCycle(self, head):
- """
- :type head: ListNode
- :rtype: ListNode
- """
- if head is None:
- return None
- slow, fast, new_node = head, head, head
- while(fast.next and fast.next.next):
- slow = slow.next
- fast = fast.next.next
- if slow == fast:
- while slow != new_node:
- new_node = new_node.next
- slow = slow.next
- return new_node
- return None
来源: https://www.cnblogs.com/rgvb178/p/9835510.html