Remove Duplicate Values From a Sorted Linked List
Solve this Problemhead of a sorted singly linked list, collapse every run of equal values down to a single node, and return the resulting (still sorted) list.
Since the list arrives sorted, any two nodes holding the same value are guaranteed to sit right next to each other — there's no need to search the whole list for matches. The optimal solution uses this adjacent-duplicate checkAdjacent-Duplicate CheckWhen a sequence is sorted, every group of equal values forms one contiguous run. Detecting a duplicate then only requires comparing each element to its immediate neighbor, rather than checking it against everything seen so far.: one pointer walks the list, and whenever the very next node repeats the current value, it's unlinked in place — no extra memory, no full re-scan.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes in head ≤ 300 - ◆
-100 ≤ node value ≤ 100 - ◆
head is sorted in non-decreasing order
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public Node removeDuplicatesFromSorted(Node head) { |
| 3 | Node curr = head; |
| 4 | while (curr != null && curr.next != null) { |
| 5 | if (curr.next.val == curr.val) { |
| 6 | curr.next = curr.next.next; |
| 7 | } else { |
| 8 | curr = curr.next; |
| 9 | } |
| 10 | } |
| 11 | return head; |
| 12 | } |
| 13 | } |
| 14 |
1curr starts at head — it walks forward, only advancing past nodes that are confirmed unique.
Approach & Solutions
Brute Force — Collect Into an Array, Skip Adjacent Duplicates, Rebuild
GoodWalk the list once, copying each value into a new array — but only when it differs from the last value copied. Since the list is sorted, comparing against just the last-added value is enough to catch every duplicate. Then build a brand-new list from that array. Correct, but it throws away the original nodes entirely and pays for a second array just to hold the result.
O(n)O(n)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node removeDuplicatesFromSorted(Node head) {
9 List<Integer> vals = new ArrayList<>();
10 Node curr = head;
11 while (curr != null) {
12 if (vals.isEmpty() || vals.get(vals.size() - 1) != curr.val) {
13 vals.add(curr.val);
14 }
15 curr = curr.next;
16 }
17 Node dummy = new Node(0);
18 Node tail = dummy;
19 for (int v : vals) {
20 tail.next = new Node(v);
21 tail = tail.next;
22 }
23 return dummy.next;
24 }
25}Optimal — Single Pointer, Skip Nodes In Place
OptimalBecause the list is sorted, a node's only possible duplicate is the one right after it. Walk with a single pointer curr: whenever curr.next holds the same value as curr, unlink it by pointing curr.next past it — and stay put, in case there are more copies of the same value ahead. Otherwise, curr has no duplicate immediately after it, so advance. No new nodes, no extra memory.
O(n)O(1)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node removeDuplicatesFromSorted(Node head) {
9 Node curr = head;
10 while (curr != null && curr.next != null) {
11 if (curr.next.val == curr.val) {
12 curr.next = curr.next.next;
13 } else {
14 curr = curr.next;
15 }
16 }
17 return head;
18 }
19}