Linked List Cycle II

Problem: Linked List Cycle II

First, we can use two pointers, one fast and one slow, to find whether there's cycle in the linked list. If these two pointers meet together, we use another two pointers with same speed, one running from the meeting point, the other running from the head. The node these two pointers meet is our answer.

To simply prove this method, you can imagine both the first meeting point and the head as start point in a cycle track. The first time we assume two runners, one runs 1 step each time, the other runs 2 steps each time. Definitely they will come back to the starting point again when the slow runner runs for 1 round and the fast runs for 2 rounds. The second time we use two pointers, we assume there's an extra straight track connected to the cycle track and what we want is the connected point.

Code in Python:

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