Find Loop [Hard]
- Method 1

Find Loop [Hard]

Write a function that takes in the head of a Singly Linked List that contains a loop (in other words, the list’s tail node points to some node in the list instead of None / null). The function should return the node (the actual node–not just its value) from which the loop originates in constant space.
Each LinkedList node has an integer value as well as a next node pointing to the next node in the list.

**Sample Input **

head = 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 // the head node with value 0
                           ^         v
                           9 <- 8 <- 7

**Sample Output **

4 -> 5 -> 6 // the node with value 4
^         v
9 <- 8 <- 7

Hints

Hint 1

Try traversing the linked list with two pointers, one iterating through every single node in the list and another iterating through every other node in the list (skipping a node every time). Eventually, both pointers will point to the same node since there is a loop in the list and since one pointer is moving faster than the other. Stop once the pointers overlap each other. How can you find the origin of the loop from here?

Hint 2

Can you come up with a mathematical relation between the respective distances traveled by each pointer? How far will the first pointer have traveled when the pointers overlap? What about the second pointer? How can this relation then help you find the actual origin of the loop in the list?

Hint 3

Let D be the distance between the start of the linked list and the origin of the loop in the list. Let P be distance between the origin of the loop and the node N where the first and second pointers overlap (going in the primary direction of the list). By the time the pointers reach N, the first pointer will have traveled a distance of length D + P, and the second pointer will have traveled a distance of length 2D + 2P, since it will have traveled twice as much as the first pointer. Thus, the distance between N and the origin of the loop (going in the primary direction of the list) can be arithmetically deduced to be 2D + 2P - D - 2P = D. With both pointers D length away from the origin of the loop, how can you find the origin?

Method 1

【O(n)time∣O(1)space】

package LinkedLists;

/**
 * @author zhengstars
 * @date 2023/06/22
 */
public class FindLoop {
    public static class ListNode {
        int value;
        ListNode next;

        public ListNode(int value) {
            this.value = value;
            this.next = null;
        }
    }

    public static ListNode findLoopStart(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        // Flag to indicate if a loop exists
        boolean hasLoop = false;

        // Finding the meeting point
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                hasLoop = true;
                break;
            }
        }

        // If no loop exists, return null
        if (!hasLoop) {
            return null;
        }

        // Resetting slow pointer to the head, keeping fast pointer at the meeting point
        slow = head;

        // Finding the start node of the loop
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    public static void main(String[] args) {
        // 构造链表
        ListNode head = new ListNode(0);
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
        ListNode node8 = new ListNode(8);
        ListNode node9 = new ListNode(9);

        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;
        node8.next = node9;
        node9.next = node4;  // Creating the loop

        // Finding the start node of the loop
        ListNode loopStart = findLoopStart(head);

        // Printing the result
        ListNode currentNode = loopStart;
        while (true) {
            System.out.print(currentNode.value + " -> ");
            currentNode = currentNode.next;
            if (currentNode == loopStart) {
                System.out.print(currentNode.value + " (Loop Start)");
                break;
            }
        }
    }
}

Find Loop [Hard]

Method 1

Enjoy Reading This Article?