Find the first node of loop in linked list

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Find the node where the cycle begins in linked list.

See our study guide for structured GFG and LeetCode practice.

Intuition

Find the node where the cycle begins in linked list. Floyd then entry-point trick.

Algorithm

1Detect cycle with Floyd. Reset slow to head. Advance both slow and fast one step at a time. They meet at cycle start.

Common Pitfalls

• Same as LC 142. Mathematical proof: distance from head to cycle entry = distance from meeting point to cycle entry.

Find the first node of loop in linked list.java

Java

// Approach: Floyd's algorithm to detect cycle. After meeting, reset one pointer to head; advance both by 1.
// They meet at the loop start.
// Time: O(n) Space: O(1)
class Node {
    int data;
    Node next;

    Node(int x) {
        data = x;
        next = null;
    }
}

class Solution {
    public static Node findFirstNode(Node head) {
        Node slow = head;
        Node fast = head;

        // Step 1: Detect the loop using Floyd's Cycle Detection
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            // If slow and fast meet, a loop is detected
            if (slow == fast)
                break;
        }

        // If no loop is detected, return null
        if (fast == null || fast.next == null)
            return null;

        // Step 2: Find the starting node of the loop
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        // The node where slow and fast meet is the start of the loop
        return slow;
    }
}

Was this solution helpful?