問題描述

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?

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?

問題分析

兩個題目結(jié)合來看，目的是判斷一個鏈表是否有環(huán)并求環(huán)的入口。
核心思路是使用快慢指針，快指針每次走兩步，慢指針每次走一步，通過兩者的相遇進(jìn)行判斷和求解。

huan.png

判斷是否有環(huán)
快慢指針都從head出發(fā)，快指針每次走兩步，慢指針每次走一步。如果快指針走到了None，說明鏈表是無環(huán)的，如果鏈表是有環(huán)的，快指針應(yīng)該一直在環(huán)上繞圈。當(dāng)慢指針也進(jìn)入環(huán)中后，每次快指針更接近慢指針一步，因此兩針會在環(huán)上相遇，即可結(jié)束判斷。

求環(huán)的入口
鏈表如上圖所示，無環(huán)長度為x，兩針相遇點距環(huán)入口距離為y，設(shè)環(huán)長為s，相遇前快指針已在環(huán)上繞了n圈，因為快指針?biāo)俣仁锹羔樀膬杀叮虼擞械仁剑?br> 2 * (x + y) = x + y + ns
即 x + y = ns, x = ns - y = (n-1) * s + (s - y) 此處n至少是為1的，因為快指針需要從后面追上慢指針。
因此讓慢指針繼續(xù)從初次相遇位置接著繞圈，快指針回到head，每次兩指針都只走一步，則相遇位置就是環(huán)的入口。

AC代碼

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return False
        p_slow = head
        p_fast = head.next
        while p_fast and p_fast.next:
            p_slow = p_slow.next
            p_fast = p_fast.next.next
            if p_fast == p_slow:
                return True
        return False

Runtime: 78 ms, which beats 83.41% of Python submissions.

# 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
        p_fast = head
        p_slow = head
        flag = False
        while p_fast and p_fast.next:
            p_slow = p_slow.next
            p_fast = p_fast.next.next
            if p_slow == p_fast:
                flag = True
                break
        if not flag:
            return None
        p_fast = head
        while True:
            if p_fast == p_slow:
                return p_fast
            p_fast = p_fast.next
            p_slow = p_slow.next

Runtime: 82 ms, which beats 75.09% of Python submissions.