Start learning free

LESSON 272 OF 338 · LINKED LISTS

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

    GO · LINKED LISTS

    Remove Linked List Elements in Go, explained

    Problem overview

    The function remove receives the head of a singly linked list of *ListNode values and an integer val. It must delete every node whose Val equals val and return the head of the resulting list. For [1, 2, 6, 3, 4, 5, 6] and val = 6 the answer is [1, 2, 3, 4, 5].

    The statement asks for O(n) time and O(1) extra space, so the list has to be edited in place, with a single pass and no copy.

    Approach: stand one node behind the one you test

    In a singly linked list, deleting a node means changing the Next of the node before it so that it skips the victim: before.Next = before.Next.Next. That has two consequences.

    First, the walking pointer must stand on the node before the one being examined. It reads node.Next.Val to decide, and edits node.Next to delete.

    Second, the head has no node before it. If the head itself has to go, a plain walk needs a special case that moves head forward, possibly several times. A dummy node removes the special case: create an empty node in front of the list, so that every real node, the head included, has a predecessor. At the end, dummy.Next is the head of the cleaned list, whether or not the original head survived.

    One more detail matters. After deleting a node, the walking pointer must stay where it is. The node that took the deleted one's place may also match. In [6, 6], advancing after the first removal would step over the second 6.

    Here is the walk on [1, 6, 6, 2] with val = 6. The list is written with the dummy in front, and the pointer node is named for the node it stands on.

    1. node is the dummy and node.Next is 1. It isn't 6, so node moves to 1.
    2. node.Next is the first 6. It matches, so 1 is linked straight to the second 6. The list is now dummy, 1, 6, 2 and node stays on 1.
    3. node.Next is the remaining 6. It matches, so 1 is linked to 2.
    4. node.Next is 2. It doesn't match, so node moves to 2. Then node.Next is nil and the loop ends.

    The result is dummy.Next, the list [1, 2].

    Step by step

    1. Create the dummy. &ListNode{} builds a new node with zero values and gives back a pointer to it, which dummy stores.
    2. Link it to the list: dummy.Next = head. The dummy now sits in front of the first real node.
    3. Start node at the dummy. It always stands on the node before the one under inspection.
    4. Loop while node.Next != nil. This is Go's way of writing a while: a for with just a condition. It stops when there is no node left to inspect.
    5. Compare node.Next.Val with val.
    6. On a match, unlink: node.Next = node.Next.Next. Do not advance, because the new node.Next hasn't been checked yet.
    7. Otherwise, advance: node = node.Next. Only a node that is kept becomes the new "node before".
    8. Return dummy.Next, which is the real head after all removals.

    The solution in Go

    func remove(head *ListNode, val int) *ListNode {
	dummy := &ListNode{}
	dummy.Next = head
	node := dummy
	for node.Next != nil {
		if node.Next.Val == val {
			node.Next = node.Next.Next
		} else {
			node = node.Next
		}
	}
	return dummy.Next
}

    Go details worth knowing:

    • Composite literals and &. ListNode{} is a struct value with every field at its zero value: Val is 0 and Next is nil. Putting & in front gives a *ListNode. The dummy's Val is never read, so its 0 doesn't matter.
    • Dot syntax through pointers. node.Next.Next chains field accesses on pointers with no special operator. If an intermediate pointer is nil, the program panics with a nil pointer dereference. Here node.Next != nil is checked by the loop condition before the body reads node.Next.Val.
    • Memory. Unlinked nodes are not freed by hand. Once nothing points to them, the garbage collector reclaims them.

    Complexity

    Time: O(n). Every iteration either removes a node or moves node one step forward, so the loop runs at most n times, with constant work in each.

    Space: O(1). The only extra memory is the dummy node and the node pointer.

    Edge cases and common mistakes

    • Removing the head. Because the dummy precedes the head, deleting it is the same assignment as deleting any other node. [6, 1] with val = 6 returns [1].
    • Consecutive matches. [1, 2, 6, 6, 3] with val = 6 returns [1, 2, 3]. A version that deletes on a match and then always executes node = node.Next moves onto the second 6 instead of checking it, so it leaves that 6 in place and returns [1, 2, 6, 3].
    • Every node matches. [7, 7, 7] with val = 7 leaves only the dummy, so dummy.Next is nil and the function returns an empty list.
    • Empty list. With head == nil, dummy.Next is nil, the loop doesn't run and the function returns nil.
    • Returning head instead of dummy.Next. If the original head was removed, head still points at a node that is no longer in the list.
    • No match at all. Every node is kept, and the returned list is the original one, untouched.

    Testing

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