题目
给定一个链表,如果链表中存在环,则返回到链表中环的起始节点,如果没有环,返回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圈后到达环入口,即两根指针在环的入口处相遇。
代码
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param: head: The first node of linked list.
@return: The node where the cycle begins. if there is no cycle, return null
"""
def detectCycle(self, head):
slow = head
fast = head
meet = None
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
meet = fast
break
if not fast or not fast.next:
return None
slow = head
while slow != meet:
slow = slow.next
meet = meet.next
return slow