Linked List Cycle II

Question

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.

Tag

• Linked List
• Two Pointers

Thought

There are two ways to solve the problem:

1. Use a visited set to mark all the visited nodes, once the pointer find a visited node, it is the start node for the cycle.
2. Use two pointer algorithm. There is a mathematical equation within this problem:

Suppose the distance between the encountered node and the start node of the cycle is l1, and the distance between the start node and the head node of the linked list is l2. Then the distance of l1 is equal to l2.

Code

Use set

# 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
        """
        # Use set
        visited = set()
        ptr = head
        while ptr is not None:
            if ptr in visited:
                return ptr
            else:
                visited.add(ptr)
                ptr = ptr.next
        return None

Use two pointers

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