Remove a Loop in a Linked List

Given the head of a singly linked list that may contain a cycle, remove the cycle — without deleting any node — and return the head of the resulting (now normal, terminating) list. This builds directly on Floyd's Cycle Detection: once slow and fast meet inside the cycle, the same distance property that locates the loop's first node can instead locate its last node — the one whose next pointer is the cyclic edge itself. Setting that single pointer to null is enough; no node is copied, moved, or deleted.

Test Case 1:

Input:head = [3, 2, 0, -4], pos = 1

Output:[3, 2, 0, -4]

Explanation:The cyclic edge is removed; every original value remains, now in a normal terminating list.

Test Case 2:

Input:head = [1, 2], pos = 0

Output:[1, 2]

Explanation:The whole list was the cycle — after removal, it's a normal 2-node list.

Test Case 3:

Input:head = [1], pos = -1

Output:[1]

Explanation:No loop to remove — the list is returned unchanged.

Constraints

◆0 ≤ number of nodes in head ≤ 10⁴
◆-10⁹ ≤ node value ≤ 10⁹
◆A cyclic test list is described as (vals, pos) — the last node's next points back to index pos (0-indexed); pos = -1 means no cycle
◆No node is deleted — only the cyclic edge is unlinked, so the returned list has the same values in the same order

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

head (list values) — 1-7 integerspos (0-indexed cycle target, -1 for none)

1	class Solution {
2	public Node removeLoop(Node head) {
3	if (head == null) {
4	return head;
5	}
6	Node slow = head, fast = head;
7	boolean hasLoop = false;
8	while (fast != null && fast.next != null) {
9	slow = slow.next;
10	fast = fast.next.next;
11	if (slow == fast) {
12	hasLoop = true;
13	break;
14	}
15	}
16	if (!hasLoop) {
17	return head;
18	}
19	if (slow == head) {
20	while (fast.next != slow) {
21	fast = fast.next;
22	}
23	} else {
24	slow = head;
25	while (slow.next != fast.next) {
26	slow = slow.next;
27	fast = fast.next;
28	}
29	}
30	fast.next = null;
31	return head;
32	}
33	}
34

1

2

3

4

5

6

7

null

Variables

head1 (node 0)

COMPARE

head is not null, so skip the empty-list base case.

Step 1 / 19

Approach & Solutions

Brute Force — Hash Set to Find the Node Whose Next Repeats, Then Snip

Good

Walk the list while tracking prev (the node right before curr). Add each node to a hash set as it's visited. The moment curr is a node that's already in the set, prev must be the true last node of the cycle — the one whose next pointer creates the loop — so set prev.next to null. Correct, but storing every visited node costs O(n) extra space.

TimeO(n)

SpaceO(n)

Java

Try it out

// Node definition used in this problem:
// class Node {
//     int val;
//     Node next;
// }

class Solution {
    public Node removeLoop(Node head) {
        Set<Node> visited = new HashSet<>();
        Node curr = head;
        Node prev = null;
        while (curr != null) {
            if (visited.contains(curr)) {
                prev.next = null;
                return head;
            }
            visited.add(curr);
            prev = curr;
            curr = curr.next;
        }
        return head;
    }
}

Optimal — Floyd's Algorithm to Locate and Snip the Loop

Optimal

Phase 1: run slow/fast pointers until they meet inside the cycle (or fast reaches the end — no loop). Phase 2: if the meeting point is head itself, walk one pointer all the way around the cycle until its next is the meeting point. Otherwise, reset slow to head and advance both pointers one step at a time until slow.next equals fast.next — at that moment fast is sitting on the true last node of the cycle. Either way, set that node's next to null.