You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
"""Definition of ListNodeclass ListNode(object): def __init__(self, val, next=None): self.val = val self.next = next"""classSolution:
""" @param: head: The first node of linked list. @return: The node where the cycle begins. if there is no cycle, return null """defdetectCycle(self, head):
slow=headfast=headmeet=Nonewhilefastandfast.next:
slow=slow.nextfast=fast.next.nextifslow==fast:
meet=fastbreakifnotfastornotfast.next:
returnNoneslow=headwhileslow!=meet:
slow=slow.nextmeet=meet.nextreturnslow
The text was updated successfully, but these errors were encountered:
题目
给定一个链表,如果链表中存在环,则返回到链表中环的起始节点,如果没有环,返回null。
要求:不使用额外空间。
例子:带环链表
1->5->3->4->6->(index-2)
,返回值为index-2
对应的节点,即值为5
的那个节点。题解
这道题可以说是链表题目中的经典题目了。解这道题之前,还有道题(LintCode No.102)是判断一个链表是否有环,使用了快慢指针的方法,具体思路是使用两根指针以不同的速度遍历链表,快指针一次走两个节点,慢指针一次走一个节点,如果两根指针中途相遇了,那么这个链表就是有环的。
本题的思路依然是使用快慢指针的方法,但前提要先利用快慢指针的特性,找出快慢指针走过的路程、环入口、相遇点之间的数学关系。
设起点到入口走了
x
步,入口到两根指针第一次相遇处走了y
步,环的长度为c
,则快慢指针第一次相遇时,快指针走的距离是慢指针的两倍,即x+Nc+y=2(x+y)
(其中N为自然数),变换一下得到x+y=Nc
,于是我们就可以得到入口的索引x=Nc-y
,这个式子意味着,如果我们用另外两根指针去遍历该链表,其中一根从起点开始走,另外一根从之前快慢指针相遇的地方开始走,并且两根指针每次都只走一步,那么当第一根指针走了x
步到达环入口时,恰好等于另一根指针从相遇点出发然后绕环N圈后到达环入口,即两根指针在环的入口处相遇。代码
The text was updated successfully, but these errors were encountered: