Start learning free

LESSON 277 OF 347 · LINKED LISTS

Remove Linked List Elements in C#: 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

    C# · LINKED LISTS

    Remove Linked List Elements in C#, explained

    Problem overview

    The method Remove receives the head of a singly linked list and an integer val. It must delete every node whose val field equals the given value and return the head of the resulting list. For [1, 2, 6, 3, 4, 5, 6] with val = 6, the answer is [1, 2, 3, 4, 5].

    The list is changed in place, in O(n) time with O(1) extra space. The returned head can be a different node from the one passed in, for example when the first nodes are the ones being removed.

    Approach: always stand one node before the candidate

    To delete a node in a singly linked list, you change the next of the node before it so that it skips over the unwanted node: before.next = before.next.next. So the loop should stand on the node before the one it is examining, and look at node.next.val.

    That works for every node except the head, because the head has no node before it. Handling the head separately means a loop just to drop leading matches, then a second loop for the rest. A dummy node avoids that. Create an empty node and point its next at the head. Now every real node, including the head, has a predecessor, and one loop handles them all. At the end the cleaned list starts at dummy.next, which is the new head whether or not the old head was removed.

    There is one subtlety: after removing a node, the walker must not move. The node that took its place might also match. In 1 -> 6 -> 6 -> 2 with val = 6, standing on 1 you remove the first 6 and the second 6 is now node.next. Only when node.next is a keeper do you advance.

    Walking through [1, 2, 6, 3, 4, 5, 6]:

    • The walker starts on the dummy. The next values 1 and 2 are kept, so it advances to 1 and then to 2.
    • On 2, the next value is 6, so the link is rewired to skip it: 2 -> 3. The walker stays on 2, and the new next value, 3, is a keeper.
    • The walker advances over 3, 4 and 5. On 5, the next value is 6, so 5 now points to null.
    • Now node.next is null, the loop ends, and dummy.next is the node 1. The list is 1 -> 2 -> 3 -> 4 -> 5.

    Step by step

    1. Create the dummy node with new ListNode() and store it in a variable declared with var. It sits in front of head.
    2. Link it to the list by setting dummy.next = head.
    3. Start the walker with var node = dummy. It always stands on the node before the one being examined.
    4. Loop while node.next != null, which means there is still a candidate to look at.
    5. Test the candidate: is node.next.val equal to val?
    6. If it matches, unlink it with node.next = node.next.next and do not advance.
    7. Otherwise, in the else branch, advance with node = node.next.
    8. Return dummy.next, the head of the cleaned list.

    The solution in C#

    class Solution {
    public ListNode Remove(ListNode head, int val) {
        var dummy = new ListNode();
        dummy.next = head;
        var node = dummy;

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

        return dummy.next;
    }
}

    C# details worth knowing

    • var infers the type. var dummy = new ListNode(); makes dummy a ListNode, and var node = dummy; does too. The variable is still statically typed, and the compiler fills in the name.
    • Parameter name val. The method's parameter and the node's field are both called val. They never clash, because the field is always reached through a node (node.next.val), while the bare name val is the parameter.
    • Unlinked nodes are reclaimed. Once nothing refers to a removed node, the garbage collector frees it. No manual deletion is needed in C#.
    • Reference semantics. The dummy's val is the default 0, but it is never compared, because the loop only reads node.next.val, and the dummy is never the next of any node.

    Complexity

    Every pass through the loop either removes a node or advances past one, so each original node is handled exactly once and the loop runs at most n times: O(n) time overall. Only the dummy node and one walking reference are added, so the extra space is O(1).

    Edge cases and common mistakes

    • Removing the head. The dummy makes this ordinary. For [7, 7, 7] with val = 7 the result is empty: dummy.next ends up null.
    • Consecutive matches. For [1, 6, 6, 2] with val = 6, the result is [1, 2]. This only works because the walker stays put after a removal.
    • Advancing after every step. If you move node forward even after unlinking, the second of two adjacent matches is skipped and stays in the list.
    • An empty list. A null head is fine here: the dummy's next is null, the loop doesn't run, and the method returns null.
    • No matches. The loop just walks to the end and the original list comes back unchanged.
    • Returning head. If the first node was removed, head still refers to the removed node. Return dummy.next.
    • Comparing nodes instead of values. Write node.next.val == val. Comparing node.next == val is a type error.

    Testing

    Results from running the solution:

    • [1, 2, 6, 3, 4, 5, 6] with 6 returns [1, 2, 3, 4, 5].
    • [7, 7, 7] with 7 returns an empty list.
    • [1, 6, 6, 2] with 6 returns [1, 2].
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free