首页 / 算法 / 【算法分析】如何理解快慢指针?判断linked list中是否有环、找到环的起始节点位置。以Leetcode 141. Linked List Cycle, 142. Linked List Cycl
【算法分析】如何理解快慢指针?判断linked list中是否有环、找到环的起始节点位置。以Leetcode 141. Linked List Cycle, 142. Linked List Cycl
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【算法分析】如何理解快慢指针?判断linked list中是否有环、找到环的起始节点位置。以Leetcode 141. Linked List Cycle, 142. Linked List Cycl,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3140字,纯文字阅读大概需要5分钟。
内容图文
快慢指针简述
快慢指针经常用于链表(linked list)中环(Cycle)相关的问题。
- 快指针(fast pointer)和慢指针(slow pointer)都从链表的head出发。
- slow pointer每次移动一格,而快指针每次移动两格。
- 如果快慢指针能相遇,则证明链表中有环;否则没有。
快慢指针的具体代码(C++, Python, Java版本)可以参考这个链接。
LeetCode中对应题目分别是:
- 141. 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\]
由离散数学中的定理可知\[(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
内容总结
以上是互联网集市为您收集整理的【算法分析】如何理解快慢指针?判断linked list中是否有环、找到环的起始节点位置。以Leetcode 141. Linked List Cycle, 142. Linked List Cycl全部内容,希望文章能够帮你解决【算法分析】如何理解快慢指针?判断linked list中是否有环、找到环的起始节点位置。以Leetcode 141. Linked List Cycle, 142. Linked List Cycl所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。