LintCode 困难题赏 - 103.寻找带环链表入口

题目

给定一个链表，如果链表中存在环，则返回到链表中环的起始节点，如果没有环，返回null。

要求：不使用额外空间。
例子：带环链表1->5->3->4->6->(index-2)，返回值为index-2对应的节点，即值为5的那个节点。

题解

这道题可以说是链表题目中的经典题目了。解这道题之前，还有道题（LintCode No.102）是判断一个链表是否有环，使用了快慢指针的方法，具体思路是使用两根指针以不同的速度遍历链表，快指针一次走两个节点，慢指针一次走一个节点，如果两根指针中途相遇了，那么这个链表就是有环的。

本题的思路依然是使用快慢指针的方法，但前提要先利用快慢指针的特性，找出快慢指针走过的路程、环入口、相遇点之间的数学关系。

设起点到入口走了x步，入口到两根指针第一次相遇处走了y步，环的长度为c，则快慢指针第一次相遇时，快指针走的距离是慢指针的两倍，即x+Nc+y=2(x+y)（其中N为自然数），变换一下得到x+y=Nc，于是我们就可以得到入口的索引x=Nc-y，这个式子意味着，如果我们用另外两根指针去遍历该链表，其中一根从起点开始走，另外一根从之前快慢指针相遇的地方开始走，并且两根指针每次都只走一步，那么当第一根指针走了x步到达环入口时，恰好等于另一根指针从相遇点出发然后绕环N圈后到达环入口，即两根指针在环的入口处相遇。

代码

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""


class Solution:
    """
    @param: head: The first node of linked list.
    @return: The node where the cycle begins. if there is no cycle, return null
    """
    def detectCycle(self, head):
        slow = head
        fast = head
        meet = None
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                meet = fast
                break
        if not fast or not fast.next:
            return None
        slow = head
        while slow != meet:
            slow = slow.next
            meet = meet.next
        return slow