243. Delete Loop in a Linked List

A singly linked list has n node values. Its last node's next pointer is connected back to the node at 0-indexed position pos (or there is no loop if pos is -1). Remove the loop, if any, by breaking that back-link, and print the resulting list's values in their original order.

Input: The first line contains an integer n. The second line contains n space-separated integers, the list's values. The third line contains pos, the 0-indexed position the last node's next pointer connects back to (or -1 if there is no loop). Output: Print the list's values in their original order, space-separated, on one line, after removing any loop.

1 <= n <= 10^5, -1 <= pos < n

Removing the loop never changes the forward sequence of values you'd print by walking from the head - it only stops the traversal from continuing forever, since the loop's nodes were already going to be visited in the same order either way.

Given a linked list with a loop, remove the loop by breaking the one back-link causing it. Brute force: Keep a hash set of visited nodes, and the moment you'd revisit a node, that means the PREVIOUS node (whose next pointer led there) is the one to null out - this works but costs O(n) extra memory. Optimised: Reusing the exact same 'find the loop's starting node' technique (Floyd's algorithm plus the reset-to-head trick) directly identifies which node comes right BEFORE the start of the loop - that node's next pointer is precisely the one link that needs to be broken, achieved with zero extra memory.

Instead of an external hash set, temporarily mark each node as visited using a spare field on the node itself (or by mutating the value/pointer in a reversible way) as it is traversed; the loop is detected the moment a node already marked visited is reached. A second pass then finds the node whose next pointer targets that marked node and nulls it out. This avoids the O(n) hash-set memory of the brute-force approach by trading it for direct in-place bookkeeping on the nodes themselves. Time: O(n) Space: O(1)

Traverse the list from the head, adding each visited node's reference to a hash set; if a node is ever encountered that is already in the set, that node is where the loop begins. Once that node is identified, scan through the list again to find the node whose next pointer points at it (the last node) and set that pointer to null, removing the loop. This is straightforward and correct but requires storing a reference to every node visited before the loop is found. Time: O(n) Space: O(n)

Use two pointers, one moving one node at a time and the other two nodes at a time; if a loop exists they are guaranteed to eventually meet inside it. Once they meet, reset one pointer to the head and advance both one step at a time - they meet again exactly at the loop's starting node. From there, walk forward until the node just before the loop start is found (the one whose next pointer equals the start node) and set its next pointer to null. This achieves the same linear time and constant space as in-place marking but without needing to mutate or add any field to the nodes themselves, making it the most general and widely used solution. Time: O(n) Space: O(1)

1. First locate the loop using Floyd's cycle detection (slow/fast pointers). 2. Find the LAST node of the loop - the one whose next pointer needs to be set to null - which is the node immediately BEFORE the loop's starting node. 3. Set that node's next pointer to null, breaking the loop; the forward sequence of values from the head remains completely unaffected otherwise.

Time: O(n) - detecting the loop and locating the node to unlink are both linear. Space: O(1) - just pointers, no extra data structure.

pos = -1, where there is nothing to remove and the list prints unchanged (per the hints); pos = 0, where the entire list is one loop; n = 10^5 for performance.

Be ready to explain the subtlety of finding the node whose NEXT pointer needs nulling (the node just before the loop start), not the loop start itself - a common point of confusion.