问题描述

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?

问题分析

两个题目结合来看，目的是判断一个链表是否有环并求环的入口。
核心思路是使用快慢指针，快指针每次走两步，慢指针每次走一步，通过两者的相遇进行判断和求解。

huan.png

判断是否有环
快慢指针都从head出发，快指针每次走两步，慢指针每次走一步。如果快指针走到了None，说明链表是无环的，如果链表是有环的，快指针应该一直在环上绕圈。当慢指针也进入环中后，每次快指针更接近慢指针一步，因此两针会在环上相遇，即可结束判断。

求环的入口
链表如上图所示，无环长度为x，两针相遇点距环入口距离为y，设环长为s，相遇前快指针已在环上绕了n圈，因为快指针速度是慢指针的两倍，因此有等式：
2 * (x + y) = x + y + ns
即 x + y = ns, x = ns - y = (n-1) * s + (s - y) 此处n至少是为1的，因为快指针需要从后面追上慢指针。
因此让慢指针继续从初次相遇位置接着绕圈，快指针回到head，每次两指针都只走一步，则相遇位置就是环的入口。

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.