Delete a Value From a Linked List

Given the head of a singly linked list and a value, delete the first node that holds that value, and return the head. If no node holds the value, return the list unchanged.

Example 1

Text

Input:  1 -> 2 -> 3 -> 2, value = 2
Output: 1 -> 3 -> 2
Explanation: only the first 2 is removed.

graph LR
    A["1"] --> B["2 (removed)"]
    B --> C["3"]
    C --> D["2"]
    A -. "new link" .-> C
    style B stroke-dasharray: 5 5

Example 2

Text

Input:  1 -> 2 -> 3, value = 1
Output: 2 -> 3
Explanation: deleting the head makes the second node the new head.

Brute force: recursion

Empty list: nothing to delete.
The head holds the value: the answer is the rest of the list, node.next.
Otherwise: delete from the rest of the list, reattach it, and keep the head.

Java

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

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

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

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

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

    static ListNode delete(ListNode head, int val) {
        if (head == null) return null;
        if (head.val == val) return head.next;
        head.next = delete(head.next, val);
        return head;
    }

    public static void main(String[] args) {
        System.out.println(toList(delete(fromArray(1, 2, 3, 2), 2)));
        System.out.println(toList(delete(fromArray(1, 2, 3), 1)));
        System.out.println(toList(delete(fromArray(1, 2, 3), 9)));
    }
}

Output

[1, 3, 2]
[2, 3]
[1, 2, 3]

Time: O(n). Space: O(n) for the recursion. A removed node has no references left, so the garbage collector can reclaim it. The recursion depth equals the list length, so a very long list can overflow the thread stack. List nodes here use null for "no next node" and have mutable fields, so no wrapper types are needed.

Optimal: a dummy node and a trailing pointer

Put a dummy node in front of the head and walk a pointer prev that stays one node behind the node being examined. To delete the node at prev.next, set prev.next to that node's next. Deleting the head isn't a special case, because the head is dummy.next and is handled like any other node. The method returns dummy.next.

Walkthrough with 1 -> 2 -> 3 -> 2, value 2:

step	`prev`	`prev.next`	action
1	dummy	1	no match, `prev` moves to node 1
2	node 1	2	match: `prev.next = prev.next.next` (node 3)

Node 1's next now holds node 3, and the old node 2 is unreachable.

Java

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

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

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

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

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

    static ListNode delete(ListNode head, int val) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        while (prev.next != null) {
            if (prev.next.val == val) {
                prev.next = prev.next.next;
                break;
            }
            prev = prev.next;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        System.out.println(toList(delete(fromArray(1, 2, 3, 2), 2)));
        System.out.println(toList(delete(fromArray(1, 2, 3), 1)));
        System.out.println(toList(delete(fromArray(1, 2, 3), 9)));
        System.out.println(toList(delete(null, 1)));
    }
}

Output

[1, 3, 2]
[2, 3]
[1, 2, 3]
[]

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

How the unlink line works: prev.next.next is the successor of the matching node. Assigning it to prev.next makes the previous node skip the matching node, which then has no references and is reclaimed by the garbage collector.

Variant: delete every occurrence

Remove the break, and only advance prev when the next node is kept. After a deletion, prev.next is already the following node, which still has to be checked.

Java

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

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

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

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

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

    static ListNode deleteAll(ListNode head, int val) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        while (prev.next != null) {
            if (prev.next.val == val) {
                prev.next = prev.next.next; // prev stays: the new next still has to be checked
            } else {
                prev = prev.next;
            }
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        System.out.println(toList(deleteAll(fromArray(2, 1, 2, 2, 3, 2), 2)));
    }
}

Output

[1, 3]

This is LeetCode 203: Remove Linked List Elements.

Edge cases

Empty list: returned as is.
Value in the head: the head is dummy.next, so no special case is needed.
Value in the tail: the tail's link becomes null.
Value not found: the loop reaches the end, and nothing changes.