Entry Node of a Loop in a Linked List

1. Problem Description

Given a linked list, if it contains a cycle, find the entry node of the cycle; otherwise, return null.

2. Approach

• Use a set to record visited nodes
• Fast and slow pointers: one moves two steps and the other moves one step. If there is no cycle they will not meet; if there is a cycle they will meet

3. Implementation

3.1. Set Method

• java

public class 链表中环的入口结点
{
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        // Check parameters
        if (pHead == null)
        {
            return null;
        }
        // Put Nodes into a Set
        Set<ListNode> set = new HashSet<>();
        // While traversing, check whether the Set already contains the node; if so it must be the cycle entry node
        ListNode current = pHead;
        while (current != null)
        {
            if (set.contains(current))
            {
                return current;
            }
            set.add(current);
            current = current.next;
        }

        return null;
    }
}

• go

// Time complexity: O(n)
// Space complexity: O(n). In the worst case, all nodes of the singly linked list are stored in the set
func EntryNodeOfLoop(pHead *ListNode) *ListNode {
	if pHead == nil {
		return nil
	}

	m := make(map[*ListNode]interface{})
	n := pHead
	for n != nil {
		_, ok := m[n]
		if ok {
			return n
		}
		m[n] = nil
		n = n.Next
	}

	return nil
}

3.2. Fast and Slow Pointers

// Time: O(N)
// Space: O(1)
func EntryNodeOfLoop2(pHead *ListNode) *ListNode {
	if pHead == nil {
		return nil
	}

	fast := pHead
	slow := pHead

	for slow != nil && fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			current := pHead
			for current != slow {
				current = current.Next
				slow = slow.Next
			}
			return current
		}
	}

	return nil
}

4. References

• Entry Node of a Cycle in a Linked List - NowCoder
• LCR 022. Linked List Cycle II - LeetCode