题目:
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
证明:
设
p1与p2相遇时用时为t,
p1在圈内走了n1圈
p2在圈内走了n2圈
圈长为l
起点到成环点距离为x
相遇点到起点距离为z
成环点到相遇点距离为y
则
2t - t = (n2 - n1) * l => t = (n2 - n1) * l
t + z = x + (n1 + 1) * l
t = (n2 - n1) * l
z + (n2 - n1) * l = x + (n1 + 1) * l
x = z + (n2 - 2*n1 - 1) * l
所以p1在相遇点接着走,p2从起点开始走,同时同步走下次会在成环点相遇
代码
# 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
"""
p1 = head
p2 = head
hasCycle = False
while p2 is not None:
if p2.next == p1:
hasCycle = True
p1 = p1.next
break
elif p2.next is None:
return None
p2 = p2.next.next
p1 = p1.next
if hasCycle:
p3 = head
while p1 != p3:
p1 = p1.next
p3 = p3.next
return p3
else:
return None
网友评论