Leetcode 142

Question

Solution

创建两个指针slow和fast，都指向首节点。slow每次向后移动一位，fast每次向后移动两位。如果slow和fast相同，则有环。如果fast移动到None了，则无环。

如果有环，然后就同时移动head和slow，直到两者相遇，相遇点就是环的入口点。

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