Remove Duplicates from Sorted List

1. Define the problem

Remove Duplicates from Sorted List

You are given the numbers of a sorted linked list , which means every value is smaller than or equal to the value after it. Delete every repeated value so that each number appears only once , and give back the list that is left. To keep the input and the output easy to read, this exercise takes a plain array of numbers, builds the linked list inside the function, and returns a plain array of the values that remain. Because the list is sorted, copies always sit next to each other , so you never have to search. Walk once from the front, and whenever a node and the node after it hold the same value, skip the second one.

Constraints

The number of nodes is between 0 and 300
-100 ≤ node value ≤ 100
The values are given in non-decreasing (sorted) order
The answer must keep the remaining values in their original order

Example

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

Output[1, 2, 3]

Explanation The list is 1 -> 1 -> 2 -> 3 -> 3. The second 1 and the second 3 are copies of the value before them, so both are skipped, leaving 1 -> 2 -> 3.

2. Know the words first

In plain terms

Linked list: A chain of small boxes called nodes. Each node holds a value and a pointer to the next node. There are no index numbers, so the only way to reach a node is to follow the chain from the front.
Node: One box in the chain. It stores a value (here, a number) and a link called next that points at the following box, or at nothing when it is the last box.
Head: The first node of the list. It is the only node you are handed to start from.
Unlink a node: Point the previous node past the node you want gone. Nothing is erased; the chain simply stops going through that box, so it is no longer part of the list.

3. Visualize the solution

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

head1

#21

#32

#43

#53

Statusinit

Start at the head and compare it with the node right after it.

What happens in this step

list = 1 -> 1 -> 2 -> 3 -> 3
current = head (value 1)
current.next = value 1

Both hold 1, so the second node is a duplicate and must go.

Step 1 of 6

Steps to visualize

Read the row left to right: the first cell is the head, and each cell after it is the next node.
The frame marks the node you are standing on and the node right after it.
If the two values are the same, unlink the second one — its cell turns into a dash to show it left the chain.
If the two values differ, step forward to the next node that is still in the chain.
Stop when there is no node after the current one; what is left is 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, in order from head to tail

head1

#21

#32

#43

#53

Statusinit

Start at the head and compare it with the node right after it.

What happens in this step

list = 1 -> 1 -> 2 -> 3 -> 3
current = head (value 1)
current.next = value 1

Both hold 1, so the second node is a duplicate and must go.

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 deleteDuplicates(values) {
  const head = toList(values);
  let current = head;

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

  return toArray(head);
}

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

6. Test cases

Test cases

Input	Expected	Covers
`values = [1, 1, 2, 3, 3]`	`[1, 2, 3]`	example from the description
`values = []`	`[]`	empty list, nothing to compare
`values = [7]`	`[7]`	smallest list that still has a node
`values = [2, 2, 2, 2]`	`[2]`	every node is a duplicate of the head
`values = [-3, -1, 0, 4, 9]`	`[-3, -1, 0, 4, 9]`	negative numbers and nothing to remove
`values = [1, 2, 3, 4, 5, 5, 5, 5]`	`[1, 2, 3, 4, 5]`	a longer list whose duplicates sit at the tail

Remove Duplicates from Sorted List