142.md

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?

思路：

使用快慢指针，fast和slow，fast每一次走两步，slow每一次走一步，当fast先遇到None值的时候表示无环，当fast和slow遇上的时候就是在环中。 假设相遇到的结点为temp。

假设起始点到入口点的距离为L1，入口点到temp距离为L2，那么L1+L2为slow走的距离，因为fast每次比slow多走一步，所以fast 走的距离为2*(L1+L2)==>推出环的的大小为L1+L2,且temp点走L1的距离就是入口点。

设一个新结点entry初始化为头结点，entry和temp每次走一步，相遇即是入口点。

代码：

解法1

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