LESSON 303 OF 415 · LINKED LISTS

Remove Linked List Elements in Swift: A Dummy Node, O(n) Time

Given the head of a singly linked list and an integer, remove all the nodes of the linked list whose value equals that integer, and return the new head.

Example:

Input: head = [1, 2, 6, 3, 4, 5, 6], integer = 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

Remove Linked List Elements in Swift, explained

Problem overview

The method remove(_ head: ListNode?, _ val: Int) -> ListNode? receives the head of a singly linked list and an integer. It removes every node whose val equals that integer and returns the head of the resulting list. For 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 and val = 6, it returns 1 -> 2 -> 3 -> 4 -> 5.

The target is O(n) time and O(1) extra space, so the method unlinks nodes inside the list and doesn't build a new one.

Approach: stand one node behind the one you test

To remove a node from a singly linked list, you change the next of the node before it so that it skips over the unwanted node. The walk must therefore stand on the node before the one it inspects, not on the inspected node itself.

That causes a problem at the front. If the head itself has to go, there is no node before it. The usual fix is a dummy node: a placeholder placed in front of the head, whose next is the head. Every real node now has a predecessor, so removing the head works exactly like removing any other node. At the end the answer is dummy.next, which may be a different node from the original head.

One more rule keeps the algorithm correct. After unlinking a node, the walk stays where it is, because the node that now follows may also match. Only when the next node is kept does the walk move forward. On 6 -> 6 -> 1 with val = 6, moving after each removal would skip the second 6.

Here is the walk on 1 -> 6 -> 6 -> 2 with val = 6. The walker starts on the dummy, and the next node, 1, is kept, so the walker moves onto 1. Its next node is 6, which matches, so 1 is relinked to the second 6 and the walker stays. That 6 matches too, so 1 is relinked to 2. Now the next node, 2, is kept, the walker moves onto it, it has no next node, and the loop ends with 1 -> 2. Every node was looked at once, so the work is proportional to the length of the list.

Step by step

Create the dummy: let dummy = ListNode(). It sits in front of head.
Link it to the list: dummy.next = head.
Start the walker on the dummy: var node: ListNode? = dummy. The type is spelled out as optional because the walker will later be assigned node!.next, a ListNode?.
Loop while node!.next != nil, that is, while there is a node ahead to inspect.
Test the next node: is node!.next!.val == val? The loop condition guarantees node!.next exists, so the second ! is safe.
If it matches, unlink it: node!.next = node!.next!.next. Don't move node.
Otherwise, move on: in the else branch, node = node!.next.
Return dummy.next, the head of the cleaned list.

The solution in Swift

class Solution {
    func remove(_ head: ListNode?, _ val: Int) -> ListNode? {
        let dummy = ListNode()
        dummy.next = head
        var node: ListNode? = dummy

        while node!.next != nil {
            if node!.next!.val == val {
                node!.next = node!.next!.next
            } else {
                node = node!.next
            }
        }

        return dummy.next
    }
}

Swift details worth a closer look:

let dummy can still change. ListNode is a class, so let only fixes which object dummy refers to. Its properties, such as next, can still be assigned.
Why node is optional. Without the annotation, var node = dummy would have the type ListNode, and node = node.next would not compile, because next is a ListNode?. Declaring ListNode? makes both assignments legal, at the cost of writing node! each time.
Force unwraps. Each ! crashes if the value is nil. They are safe here because node only moves onto an existing next node, and the loop condition checks that node!.next exists before the body reads it.
Chains of optionals. node!.next!.next reads the node after the one being removed, and it can be nil, which is fine: the list then ends at node.
Removed nodes are freed. Once no reference points to an unlinked node, Swift releases it automatically.

Complexity

Time: O(n). Every pass of the loop either removes a node or moves the walker one node forward, so there are at most n passes in total.

Space: O(1). One dummy node and one walker, whatever the list's length.

Edge cases and common mistakes

Matches at the head. 6 -> 6 -> 1 with val = 6 returns 1. Without the dummy node, this needs its own loop before the main one.
Every node matches. 7 -> 7 -> 7 -> 7 with val = 7 returns nil, an empty list.
An empty list. With head equal to nil, dummy.next is nil, the loop never runs, and the method returns nil.
No match. 1 -> 2 with val = 9 comes back unchanged.
Consecutive matches in the middle. 1 -> 2 -> 2 -> 3 with val = 2 returns 1 -> 3, because the walker waits after the first removal.
Moving the walker after an unlink. It skips the node that has just taken the removed node's place.
Returning head. If the original head was removed, head still refers to that unlinked node. The result must be dummy.next.
Testing the walker instead of its next node. A walker that stands on the node it tests can't unlink that node, since nothing refers back to the previous one.

Testing

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

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

Start learning free