Remove Linked List Elements

1. Define the problem

You are given the numbers of a linked list and one target number. Remove every node whose value equals the target , and give back what is left, in the same order. The function takes a plain array of numbers plus the target, builds the linked list inside, and returns a plain array of the values that survive. The tricky part is the front of the list: if the head itself must go, there is no previous node to repair. The fix is a dummy node placed in front of the head, so every real node has something before it and one rule handles the whole list.

Constraints

The number of nodes is between 0 and 10⁴
1 ≤ node value ≤ 50
0 ≤ target ≤ 50
The order of the nodes that stay must not change

Example

Inputvalues = [1, 2, 6, 3, 6], target = 6

Output[1, 2, 3]

Explanation The list is 1 -> 2 -> 6 -> 3 -> 6. Both nodes holding 6 are removed, leaving 1 -> 2 -> 3.

2. Know the words first

In plain terms

Linked list: A chain of nodes. Each node holds a value and a link to the next node, so you can only move forward, one node at a time.
Dummy node: A throwaway node glued in front of the real head. Its value is never used; it exists so the head can be deleted with the same code as any other node. At the end you return dummy.next.
Previous node: The node just before the one you are inspecting. You need it to delete a node, because deleting means telling the previous node to point further along.

3. Visualize the solution

Each cell is one node of the list, from head to tail

head1

#22

#36

#43

#56

Statusinit

The dummy node sits before the head; the first node checked is the head, holding 1.

What happens in this step

list = 1 -> 2 -> 6 -> 3 -> 6, target = 6
prev = dummy (sits before the head)
node checked = head (value 1)

1 is not 6, so this node stays and prev moves onto it.

Step 1 of 6

Steps to visualize

An invisible dummy node sits just before the head, so the head can be removed like any other node.
The frame marks the previous node and the node being checked.
If the checked value equals the target, the previous node points past it and its cell turns into a dash.
If the value is kept, the previous node moves forward onto it.
When there is nothing left to check, the surviving cells are the answer.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Each cell is one node of the list, from head to tail

head1

#22

#36

#43

#56

Statusinit

The dummy node sits before the head; the first node checked is the head, holding 1.

What happens in this step

list = 1 -> 2 -> 6 -> 3 -> 6, target = 6
prev = dummy (sits before the head)
node checked = head (value 1)

1 is not 6, so this node stays and prev moves onto it.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function toList(values) {
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) {
    head = new ListNode(values[i], head);
  }
  return head;
}

function toArray(head) {
  const out = [];
  for (let node = head; node !== null; node = node.next) {
    out.push(node.val);
  }
  return out;
}

function removeElements(values, target) {
  const dummy = new ListNode(0, toList(values));
  let prev = dummy;

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

  return toArray(dummy.next);
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`values = [1, 2, 6, 3, 6], target = 6`	`[1, 2, 3]`	example from the description
`values = [], target = 1`	`[]`	empty list, nothing to remove
`values = [7, 7, 7, 8], target = 7`	`[8]`	the head and its neighbours all match, which is what the dummy node is for
`values = [4, 4, 4], target = 4`	`[]`	every node is removed, leaving an empty list
`values = [1, 2, 3, 4, 5], target = 9`	`[1, 2, 3, 4, 5]`	the target is not in the list at all
`values = [1, 5, 2, 5, 3, 5, 4, 5], target = 5`	`[1, 2, 3, 4]`	a longer list where every second node matches

Remove Linked List Elements