Find the first node of loop in linked list

JavaView on GFG

Time: O(n)

Space: O(1)

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?