难度: 中等(Medium)

题目描述

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