Leetcode解题-Linked 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?

Linked List Cycle的升级版。要求不仅判断是否有环，而且要找出环开始的位置。

分析

对于存在环的情况，设从链表头部到环第一个元素的距离为x，从环第一个元素到两指针相遇点距离为y，环长度为r。这里可以证明的一点是，当两指针相遇时，慢指针肯定没有跑完一圈。这样来证明：当慢指针到达环第一个元素时，快指针肯定在环中某个地方，设距离环第一个元素z，肯定有z < r。而快指针只需要z步就可以追上慢指针，所以慢指针没有机会跑完一圈。

设相遇时已经走了t步，则t = x + y, 2t = x + y + nr， 其中n为正整数。则可以推导出t = nr，x = nr - y = (n - 1)r + (r - y)。这样一来，如果我们在两指针相遇后，再用一个指针从链表头开始走，直到它和慢指针相遇，相遇点就是环开始的地方。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 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 or not head.next:
            return None

        p1 = head.next
        p2 = head.next.next
        while p2:
            if not p2 or not p2.next:
                return None
            if p1 == p2:
                break
            p2 = p2.next.next
            p1 = p1.next

        if p1 == p2:
            p2 = head
            while p1 != p2:
                p1 = p1.next
                p2 = p2.next
            return p1

热评文章