Start learning free

LESSON 278 OF 348 · LINKED LISTS

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

Practice O(n) Read the full explanation

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
    Ctrl + Enter to check

    KOTLIN · LINKED LISTS

    Remove Linked List Elements in Kotlin, explained

    Problem overview

    The function remove receives the head of a singly linked list and an integer value. It removes every node whose value equals value and returns the head of the resulting list. For the list [1, 2, 6, 3, 4, 5, 6] and the value 6, the result is [1, 2, 3, 4, 5].

    The statement asks for O(n) time and O(1) extra space, so the function must relink the existing nodes in a single pass.

    Approach: unlink from the node before

    To remove a node from a singly linked list, you do not touch the node itself. You change the next of the node before it, so that it skips over the unwanted node. This means the loop must stand on the node before the one it examines, and look one step ahead.

    That raises a problem for the head. The first node has no node before it, so removing it would need its own special case, and a list in which the first several nodes all match makes that case loop. A dummy node removes the problem: a placeholder node placed in front of the head. The real head now has a predecessor, so every node is removed the same way, and the answer is whatever follows the dummy at the end.

    One rule keeps the loop correct: after you unlink a node, do not move forward. The node that now follows may match as well. Move forward only when the next node is kept.

    On [6, 6, 1] with the value 6: the dummy's next is a 6, so it is unlinked; the new next is also a 6, so it is unlinked too; then the next is 1, which stays, and the walker moves onto it. The result is [1].

    Step by step

    1. Create the dummy. Store a new empty ListNode() in a val named dummy.
    2. Link it to the list by setting dummy.next to head.
    3. Declare the walker. node is a var of type ListNode?, starting at dummy. It is nullable because later it is assigned node.next, which can be null. It always stands on the node before the one being examined.
    4. Loop while there is a next node: node!!.next != null. The !! says that node itself is never null here, which holds because the walker only moves onto a non-null next node.
    5. Compare the next node's value. Check whether node.next!!.`val` equals value. The field is named val, a Kotlin keyword, so it needs backticks.
    6. On a match, unlink it: set node.next to node.next!!.next. The walker stays where it is.
    7. Otherwise move on: set node to node.next.
    8. Return dummy.next, the head of the cleaned list. It may be different from the original head, or null if every node was removed.

    The solution in Kotlin

    class Solution {
    fun remove(head: ListNode?, value: Int): ListNode? {
        val dummy = ListNode()
        dummy.next = head
        var node: ListNode? = dummy

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

        return dummy.next
    }
}

    The Kotlin details worth a closer look:

    • The explicit type ListNode?. Without it, Kotlin would infer ListNode from dummy, and node = node.next would not compile, since node.next may be null. The annotation widens the variable's type.
    • Why !! appears twice. node!! in the loop condition asserts the walker is not null, and Kotlin then treats it as non-null for the rest of the body. node.next is a mutable property, so the compiler never smart-casts it, and node.next!! is needed wherever the code uses it as a node. The loop condition has already shown that it is not null.
    • Backticks on val. The node's field is named val, a Kotlin keyword, so it is written with backticks: node.next!!.`val`. The function's parameter is called value, which needs no such care.
    • Empty nodes. ListNode() works because the node's value has a default. The dummy's own value is never read.
    • Removed nodes. Once nothing refers to an unlinked node, the JVM's garbage collector reclaims it; there is nothing to free by hand.

    Complexity

    Time: O(n). Every pass of the loop either unlinks a node or moves the walker one node forward, and each node is handled once. The total number of passes is at most the number of nodes.

    Space: O(1). The function creates one dummy node and two references, regardless of the list size.

    Edge cases and common mistakes

    • An empty list. With head = null, the dummy's next is null, the loop does not run, and the function returns null.
    • Every node matches. [7, 7, 7] with the value 7 gives an empty list, since dummy.next ends up null.
    • The head matches. [6, 1] with the value 6 returns [1]. This is where the dummy earns its place.
    • Consecutive matches. [1, 6, 6, 2] with the value 6 must give [1, 2]. Moving the walker after an unlink would skip the second 6.
    • No match. The list comes back unchanged.
    • Returning head. If the first node was removed, head still points to it, and the result would be wrong. Return dummy.next.
    • Standing on the node being checked. A walker that stands on the matching node cannot unlink it, because only the node before it holds the link to change.

    Testing

    • [1, 2, 6, 3, 4, 5, 6] with value 6 gives [1, 2, 3, 4, 5].
    • [7, 7, 7] with value 7 gives [].
    • [] with value 1 gives [].
    • [6, 1] with value 6 gives [1].
    • [1, 6, 6, 2] with value 6 gives [1, 2].
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free