List Cycle II

题目描述

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.

Follow up:

Can you solve it without using extra space?

解题方法

画图来解释能够更好地理解题目

pic

依然是快慢指针的思路，那么快指针走的路是慢指针的两倍， 假设如图起点到开头的距离是x, 相遇点距离起点的位置是k, 圈的长度为L

  • x + m*L + k = d
  • x + n * L + k = 2d

（m, n分别代表走的圈数）

那么可得 x + k = (n-2m) * L, 也就是x = (L - k) + (n-2m-1) * L, 也就是说从开头走到cycle的start, 与从相遇点走到cycle的start的距离的差距是整数倍个圈的长度，

所以这时候再从开头出发，另一个指针从相遇点出发，它们相遇的点就是cycle的start.

Solution

# 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 not head:
            return None
        p1 = head
        p2 = head
        p3 = head
        while p2 and p2.next:
            p1 = p1.next
            p2 = p2.next.next
            if p1 == p2:
                break

        if not p2 or not p2.next:
            return None

        while p1 != p3:
            p1 = p1.next
            p3 = p3.next

        return p1

Reference