LeetCode 142 [Linked List Cycle II]

原题

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

样例
给出 -21->10->4->5, tail connects to node index 1，返回10

解题思路

• 首先跟Linked List Cycle一样，还是快慢指针，从头开始走，如果没有相遇快指针就走到尾了，则说明没有环，返回NULL
• 如果相遇了，把慢指针重新放到开头，快慢指针一起一步一步走再次相遇即是环的入口，不要问我为什么...想知道的可以去看一下数学证明

完整代码

# 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
        """
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None