Delete Node in a Linked List

1. Define the problem

Delete one node from a linked list when the only thing you are handed is that node itself — not the head, so you cannot reach the node before it. Here the function takes the list values plus the value to delete, finds that node, and then applies the trick. It returns the list that is left as a plain array. The node to delete is never the last node. The trick is that a node is only known by what it holds . Copy the next node’s value into the current node, then unlink the next node. The list ends up exactly as if the current node had been deleted.

Constraints

The list has between 2 and 1000 nodes
-1000 ≤ node value ≤ 1000
Every value in the list is different
The node to delete exists and is not the last node

Example

Inputvalues = [4, 5, 1, 9], target = 5

Output[4, 1, 9]

Explanation The node holding 5 takes the value 1 from the node after it, then that next node is unlinked, so the chain reads 4 -> 1 -> 9.

2. Know the words first

In plain terms

Linked list: A chain of nodes, each holding a value and a link to the next node. You can only move forward from wherever you are standing.
Deleting a node normally: Telling the node before it to point at the node after it. That needs the previous node, which you do not have here.
Copy-and-skip trick: Overwrite the current node’s value with the next node’s value, then link past the next node. The values that remain in the chain are the same as if the current node had been removed.

3. Visualize the solution

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

head4

#25

#31

#49

Statussearch

Start at the head, holding 4, which is not the value to delete.

What happens in this step

list = 4 -> 5 -> 1 -> 9, target = 5
node = head (value 4)

4 is not 5, so move one step along the chain.

Step 1 of 5

Steps to visualize

Walk forward until you are standing on the node whose value must go.
You cannot reach the node before it, so you cannot unlink the node you are on.
Instead, copy the value from the next node into the node you are standing on.
Then unlink that next node — its cell turns into a dash.
The chain now reads as if the original node had been deleted.

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

head4

#25

#31

#49

Statussearch

Start at the head, holding 4, which is not the value to delete.

What happens in this step

list = 4 -> 5 -> 1 -> 9, target = 5
node = head (value 4)

4 is not 5, so move one step along the chain.

Step 1 of 5

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 deleteNode(values, target) {
  const head = toList(values);
  let node = head;

  while (node !== null && node.val !== target) {
    node = node.next;
  }

  if (node === null || node.next === null) {
    return toArray(head);
  }

  node.val = node.next.val;
  node.next = node.next.next;

  return toArray(head);
}

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

6. Test cases

Test cases

Input	Expected	Covers
`values = [4, 5, 1, 9], target = 5`	`[4, 1, 9]`	example from the description
`values = [4, 5, 1, 9], target = 4`	`[5, 1, 9]`	the node to delete is the head
`values = [4, 5, 1, 9], target = 1`	`[4, 5, 9]`	the node to delete sits just before the tail
`values = [1, 2], target = 1`	`[2]`	smallest list the trick works on
`values = [-7, -3, 0, 8], target = -3`	`[-7, 0, 8]`	negative values in the list
`values = [1, 2, 3], target = 42`	`[1, 2, 3]`	the value is not in the list, so nothing changes

Delete Node in a Linked List