Detect and Remove a Loop in a Linked List

A linked list may contain a loop: its last node points back to an earlier node instead of to null. If there is a loop, remove it by setting that last node's next to null. Use no extra space.

Example

Text

Input:  1 -> 2 -> 3 -> 4 -> 5, and 5 points back to 3
Output: 1 -> 2 -> 3 -> 4 -> 5 -> null

graph LR
    A["1"] --> B["2"] --> C["3"] --> D["4"] --> E["5"]
    E -. "remove" .-> C

As in Detect a Cycle in a Linked List, next is a plain object reference, so the last node can point back to an earlier node. The build helper keeps the nodes in an array and points the last node at index pos, or at null when pos is -1.

Brute force: remember visited nodes

Walk the list with a HashSet of visited nodes. If the current node's next is already in the set, the current node is the last one in the loop: cut its link.

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    static void removeLoop(ListNode head) {
        Set<ListNode> seen = new HashSet<>(); // identity-based: ListNode does not override equals
        ListNode cur = head;
        while (cur != null) {
            seen.add(cur);
            if (cur.next != null && seen.contains(cur.next)) {
                cur.next = null;
                return;
            }
            cur = cur.next;
        }
    }

    // The last node points to index pos (or to null when pos is -1).
    static ListNode[] build(int[] values, int pos) {
        int n = values.length;
        ListNode[] nodes = new ListNode[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new ListNode(values[i]);
        }
        for (int i = 0; i + 1 < n; i++) {
            nodes[i].next = nodes[i + 1];
        }
        if (pos >= 0) nodes[n - 1].next = nodes[pos];
        return nodes;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = head; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    public static void main(String[] args) {
        ListNode[] nodes = build(new int[]{1, 2, 3, 4, 5}, 2);
        removeLoop(nodes[0]);
        System.out.println(toList(nodes[0]));
    }
}

Output

[1, 2, 3, 4, 5]

Time: O(n). Space: O(n) for the set.

Optimal: Floyd's algorithm, then find the last node

Detect: move slow one step and fast two steps at a time. If fast reaches the end, there's no loop. Otherwise they meet inside the loop.
Find the loop's start: move one pointer back to the head and advance both one step at a time. They meet at the first node of the loop. (Why this works is explained in Detect a Cycle in a Linked List.)
Find the last node: walk from the start around the loop until a node's next is the start, and set that next to null.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    static void removeLoop(ListNode head) {
        ListNode slow = head, fast = head;
        while (true) {
            if (fast == null || fast.next == null) return; // no loop
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
        }
        ListNode start = head;
        while (start != slow) {
            start = start.next;
            slow = slow.next;
        }
        ListNode last = start;
        while (last.next != start) {
            last = last.next;
        }
        last.next = null;
    }

    // The last node points to index pos (or to null when pos is -1).
    static ListNode[] build(int[] values, int pos) {
        int n = values.length;
        ListNode[] nodes = new ListNode[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new ListNode(values[i]);
        }
        for (int i = 0; i + 1 < n; i++) {
            nodes[i].next = nodes[i + 1];
        }
        if (pos >= 0) nodes[n - 1].next = nodes[pos];
        return nodes;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = head; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    public static void main(String[] args) {
        for (int pos : new int[]{2, 0, 4, -1}) {
            ListNode[] nodes = build(new int[]{1, 2, 3, 4, 5}, pos);
            removeLoop(nodes[0]);
            System.out.println((pos < 0 ? "no loop" : "pos " + pos) + ": " + toList(nodes[0]));
        }
    }
}

Output

pos 2: [1, 2, 3, 4, 5]
pos 0: [1, 2, 3, 4, 5]
pos 4: [1, 2, 3, 4, 5]
no loop: [1, 2, 3, 4, 5]

Time: O(n). Space: O(1).

Edge cases

No loop: fast reaches null, and the list is left alone.
Loop back to the head (pos = 0): the start is the head, and the last node is the tail.
Node pointing to itself (pos = 4): the start and the last node are the same node.