LESSON 278 OF 348 · LINKED LISTS

Remove Linked List Elements in TypeScript: O(n) with a Dummy Node

Given the head of a singly linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example:

Input: head = [1, 2, 6, 3, 4, 5, 6], val = 6
Output: [1, 2, 3, 4, 5]

Note:

Your algorithm should run in O(n) time and use O(1) extra space.

STEP 1 OF 8

Guided

Ctrl + Enter to check

TYPESCRIPT · LINKED LISTS

Remove Linked List Elements in TypeScript, explained

Problem overview

The method remove receives the head of a singly linked list and a number val. It removes every node whose val field equals val and returns the head of the resulting list.

For 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 and val = 6 the result is 1 -> 2 -> 3 -> 4 -> 5. The statement asks for O(n) time and O(1) extra space, so the nodes must be unlinked in place rather than copied into a new list.

Approach: unlink from the node before

A singly linked node can't remove itself. To delete a node you change the next link of the node in front of it so that the link skips over it: previous.next = previous.next.next. So the loop should stand on the node before the one it examines, look at node.next, and decide.

That raises a problem for the head. The first node has no node in front of it, and if the head itself matches, the function must return a different head. You can handle it with a separate loop that first skips matching nodes at the front, but there is a simpler way: put a dummy node in front of the list. After that, every real node has a predecessor, and the head is treated like any other node. At the end, the new head is dummy.next.

The loop then follows one rule for each position of node:

if node.next matches, unlink it and stay where you are, because the new next node may match too;
otherwise move node forward.

With 6 -> 6 -> 1 and val = 6, the dummy points at the first 6. It matches, so the dummy is relinked to the second 6. That one matches too, and the dummy is relinked to 1. Now 1 doesn't match, so node moves onto it, and the loop ends. The result is the list 1.

Step by step

Create the dummy node with new ListNode() in a variable dummy, declared with let and typed ListNode. It sits in front of the list, so removing the first node works like removing any other.
Link it to the list: dummy.next = head.
Declare node, typed ListNode, and start it at dummy. It always stands on the node before the one being examined.
Loop while node.next !== null, that is, while there is still a node to examine.
Compare node.next.val with val.
On a match, unlink: node.next = node.next.next. Do not move node. Moving would let the second of two matching nodes in a row slip through.
Otherwise, advance: node = node.next.
Return dummy.next. This is the head of the cleaned list, which may differ from the original head, or be null.

The solution in TypeScript

class Solution {
    remove(head: ListNode | null, val: number): ListNode | null {
        let dummy: ListNode = new ListNode();
        dummy.next = head;
        let node: ListNode = dummy;

        while (node.next !== null) {
            if (node.next.val === val) {
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }

        return dummy.next;
    }
}

The TypeScript details worth a closer look:

new ListNode() with no arguments. The node class used in these lessons has optional constructor parameters, so a bare node holds the value 0 and a next of null. The dummy's value is never examined, because the loop only reads node.next.val.
Types. node is typed ListNode, while next is ListNode | null. With the compiler's strict null checks on, the test node.next !== null would narrow the type so that node.next.val is accepted. The lessons compile with strict off, where null is allowed in every type, so the annotation documents the intent but the compiler doesn't enforce it. A null read still fails at run time.
=== compares numbers. node.next.val === val is a strict comparison. The annotations say both sides are numbers, but they are not checked at run time, so a value that arrived as a string from outside the program would never match.
Removed nodes are simply skipped. Nothing is freed by hand. Once no reference leads to a node, the garbage collector can reclaim it.
The input list is modified. The caller's nodes are relinked. The old head variable may now point at a node that is no longer in the list, so use the returned value.

Complexity

Time: O(n). Every iteration either removes a node or moves forward, and each node is looked at once. The total number of iterations is the number of nodes.

Space: O(1). The dummy node and the node variable are the only additions, whatever the length of the list.

Edge cases and common mistakes

Empty list. With head = null, the dummy's next is null, the loop doesn't run, and the method returns null.
Every node matches. For 7 -> 7 -> 7 and val = 7 the dummy ends up pointing at null, so the result is the empty list.
The head matches. For 6 -> 1 -> 2 and val = 6 the returned head is the node holding 1. This is the case the dummy exists for.
Consecutive matches. Moving node forward after an unlink, instead of staying put, skips the check on the next node. For 1 -> 6 -> 6 -> 2 it would leave 1 -> 6 -> 2.
No match. The list comes back unchanged, and the loop only advances.
Returning head. If the first node was removed, head still points at a node that is no longer in the list. Return dummy.next.
Checking node.val instead of node.next.val. Standing on the node you test means you can't unlink it, because you no longer have its predecessor.

Testing

[1, 2, 6, 3, 4, 5, 6] with val = 6 gives [1, 2, 3, 4, 5].
[] with val = 1 gives [].
[7, 7, 7] with val = 7 gives [].
[6, 6, 1, 6] with val = 6 gives [1].
[1, 2] with val = 5 gives [1, 2].

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free