Start learning free

LESSON 302 OF 414 · LINKED LISTS

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

Practice O(n) Read the full explanation

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

    SCALA · LINKED LISTS

    Remove Linked List Elements in Scala, explained

    Problem overview

    The method remove receives the head of a singly linked list and an integer value. It removes every node whose val equals value and returns the head of the new list. For the list 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 and value = 6, the result is 1 -> 2 -> 3 -> 4 -> 5.

    The statement asks for O(n) time and O(1) extra space, so the method changes the links of the existing list in one pass and builds no copy.

    Approach: unlink matches from the node before them

    Removing a node from a singly linked list means changing the next of the node before it, so that the link skips the removed node. A node can't remove itself, because it has no reference to its predecessor. The loop therefore stands on the node before the one it examines, and looks one step ahead with node.next.

    The head is the awkward case. It has no predecessor, and it may need to be removed, even several times in a row (6 -> 6 -> 1). Handling that separately needs extra code. A dummy node removes the problem: create a throwaway node and link it in front of the head. Now every real node, including the head, has a node before it, and the loop treats all of them the same way. At the end, dummy.next is the head of the cleaned list, whether or not the original head was removed.

    The one subtle rule: after unlinking a node, do not advance. The node that moved into node.next may also match, as with the two 6s in 6 -> 6 -> 1. Only when node.next is kept does node move forward.

    Step by step

    1. Create dummy as a new empty ListNode(), declared with val. It sits in front of head.
    2. Link it: set dummy.next to head.
    3. Start node at dummy, declared with var. It always stands on the node before the one being examined.
    4. Loop while node.next != null, that is, while there is still a node to examine.
    5. Compare the next node's value, node.next.`val`, with the parameter value. Because val is a Scala keyword, the field name is written in backticks.
    6. On a match, unlink it with node.next = node.next.next, and leave node where it is.
    7. Otherwise move on: in the else branch, set node = node.next.
    8. Return dummy.next, the head of the cleaned list.

    The solution in Scala

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

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

        dummy.next
    }
}

    The Scala details worth a closer look:

    • Backticks for val. node.next.`val` reads the field named val. Without backticks the compiler reads the keyword and reports a syntax error. The parameter is called value to avoid the same clash.
    • val dummy and var node. The dummy node reference never changes, so it is a val, even though its next field changes. node moves along the list, so it is a var.
    • ListNode() without new. Scala 3 allows calling a class like a function, and the node class has default values for its fields, so no arguments are needed.
    • Everything is a reference. The assignment node = dummy doesn't copy a node; it makes node refer to the same object. Changing node.next changes the node that dummy refers to, too, as long as the two refer to the same node.
    • The last expression is the result. dummy.next needs no return.
    • Null checks are safe here. Inside the loop body node.next isn't null, so node.next.`val` is safe. When the last node is unlinked, node.next.next is null, which correctly ends the list.

    Complexity

    Time: O(n). Each iteration either removes a node or moves node forward, and every node is examined once.

    Space: O(1). The method creates one dummy node and one extra reference, however long the list is. Removed nodes are not copied; once nothing refers to them, the JVM can reclaim them.

    Edge cases and common mistakes

    • The head matches. For 6 -> 6 -> 1 with value = 6, the loop unlinks both 6s from the dummy and returns 1. Without a dummy node, this case needs its own loop.
    • Everything matches. For 7 -> 7 -> 7 and value = 7, the result is an empty list: dummy.next is null.
    • An empty list. A null head gives dummy.next == null, the loop doesn't run, and the method returns null.
    • Nothing matches. The list is returned unchanged, because every iteration takes the else branch.
    • Consecutive matches. For 1 -> 2 -> 2 -> 1 with value = 2, the result is 1 -> 1. If node moved forward after the first removal, the second 2 would be skipped over and stay in the list.
    • Returning head. If the original head was removed, head still points at a node that is no longer in the list. Always return dummy.next.
    • Standing on the examined node. If node were the node being checked, there would be no way to relink its predecessor.

    Testing

    • 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 with value = 6 gives 1 -> 2 -> 3 -> 4 -> 5.
    • 7 -> 7 -> 7 with value = 7 gives an empty list.
    • 6 -> 6 -> 1 with value = 6 gives 1.
    • 1 -> 2 -> 2 -> 1 with value = 2 gives 1 -> 1.
    • 1 -> 2 with value = 5 gives 1 -> 2.
    • An empty list gives an empty list.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free