Log inSign up
easyLeetCodeNot Started

Remove Duplicates from Sorted List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

Given the head of a sorted linked list, *delete all duplicates such that each element appears only once*. Return the *linked list sorted as well*.

Example 1 · Example 1:

Input: head = [1,1,2]
Output: [1,2]
Explanation: Duplicate node 1 is bypassed, leaving [1, 2].

Example 2 · Example 2:

Input: head = [1,1,2,3,3]
Output: [1,2,3]
Explanation: Duplicate 1s and 3s are removed, leaving [1, 2, 3].

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Leverage pre-sorted invariant to eliminate hash set overhead.
  • Master anchor pointer retention when removing runs of multiple identical elements.
  • Safely deallocate memory for excised nodes in languages with manual memory management.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Removing duplicate entries from a pre-sorted linked list.
  • Keeping exactly one instance of each distinct value.
  • O(1) memory requirement.

Algorithmic Decision Tree:

  • Do NOT advance curr when a duplicate is found, because three or more identical numbers in a row require sequential deletions from the same anchor node.
  • Only advance curr = curr.next when curr.val != curr.next.val.

Connected Patterns:

Remove Duplicates from Sorted List II (Delete All Instances)Remove ElementRemove Duplicates from Sorted Array

1. Brute Force — Hash Set of Seen Values

Intuition

Maintain a hash set of observed values. As we traverse, if curr.next.val is in the set, bypass curr.next; otherwise add it to the set and advance.

Algorithm

  1. Step 1: If head == null, return null.
  2. Step 2: Create a HashSet containing head.val.
  3. Step 3: curr = head.
  4. Step 4: While curr.next != null:
  5. a. If set.contains(curr.next.val): curr.next = curr.next.next.
  6. b. Else: set.add(curr.next.val), curr = curr.next.
  7. Step 5: Return head.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_set>
3
4using namespace std;
5
6struct ListNode {
7 int val;
8 ListNode *next;
9 ListNode(int x) : val(x), next(nullptr) {}
10};
11
12class Solution {
13public:
14 ListNode* deleteDuplicates(ListNode* head) {
15 if (!head) return nullptr;
16 unordered_set<int> seen;
17 seen.insert(head->val);
18 ListNode* curr = head;
19
20 while (curr->next) {
21 if (seen.count(curr->next->val)) {
22 ListNode* toDelete = curr->next;
23 curr->next = curr->next->next;
24 delete toDelete;
25 } else {
26 seen.insert(curr->next->val);
27 curr = curr->next;
28 }
29 }
30 return head;
31 }
32};
33
34int main() {
35 ListNode* h = new ListNode(1);
36 h->next = new ListNode(1);
37 h->next->next = new ListNode(2);
38 h->next->next->next = new ListNode(3);
39 h->next->next->next->next = new ListNode(3);
40
41 Solution sol;
42 ListNode* res = sol.deleteDuplicates(h);
43
44 cout << "Brute Force Deduplicated: ";
45 for (ListNode* c = res; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
46 cout << endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(N) — Visits each node once in O(N). Hash set insertions and lookups take O(1).
  • Space complexity: O(N) — Allocates a hash set storing up to N distinct values.

Why Brute Force Doesn't Scale:

Hash sets allocate auxiliary buckets and incur hashing overhead.

For N = 100,000 nodes, in-place deduplication runs in <0.5ms.

2. Better — Recursive Suffix Deduplication

Intuition

Recursively deduplicate the suffix head.next. After returning, if head.val == head.next.val, return head.next; otherwise attach head.next and return head.

Algorithm

  1. Step 1: If head == null || head.next == null, return head.
  2. Step 2: Set head.next = deleteDuplicates(head.next).
  3. Step 3: If head.val == head.next.val, return head.next.
  4. Step 4: Else return head.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12public:
13 ListNode* deleteDuplicates(ListNode* head) {
14 if (!head || !head->next) return head;
15 head->next = deleteDuplicates(head->next);
16 return head->val == head->next->val ? head->next : head;
17 }
18};
19
20int main() {
21 ListNode* h = new ListNode(1);
22 h->next = new ListNode(1);
23 h->next->next = new ListNode(2);
24
25 Solution sol;
26 ListNode* res = sol.deleteDuplicates(h);
27
28 cout << "Recursive Deduplicated: ";
29 for (ListNode* c = res; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
30 cout << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N) — Recursive calls dive to tail in N frames and adjust pointers on the return path.
  • Space complexity: O(N) call stack — Recursive call stack requires O(N) memory.

3. Optimal — Single-Pass In-Place Neighbor Bypass

Intuition

Iterate curr = head. If curr.val == curr.next.val, bypass curr.next via curr.next = curr.next.next (in C++, delete the unlinked node to free memory). Do not advance curr yet. If curr.val != curr.next.val, advance curr = curr.next.

Algorithm

  1. Step 1: If head == null, return null.
  2. Step 2: Initialize curr = head.
  3. Step 3: While curr != null && curr.next != null:
  4. a. If curr.val == curr.next.val: curr.next = curr.next.next.
  5. b. Else: curr = curr.next.
  6. Step 4: Return head.

Remove Duplicates from Sorted List Master Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
First duplicate removed
Visual state
Values and pointers at this exact step
linked list
curr → 1
Node 1
1
Node 2
2
Node 3a
3
Node 3b
3
NULL
Check / comparison
1 == 1
Decision / next transition
Bypass duplicate
Why this step matters

First duplicate removed.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12public:
13 ListNode* deleteDuplicates(ListNode* head) {
14 ListNode* curr = head;
15 while (curr && curr->next) {
16 if (curr->val == curr->next->val) {
17 ListNode* duplicate = curr->next;
18 curr->next = curr->next->next;
19 delete duplicate; // Free memory in C++
20 } else {
21 curr = curr->next;
22 }
23 }
24 return head;
25 }
26};
27
28int main() {
29 ListNode* h = new ListNode(1);
30 h->next = new ListNode(1);
31 h->next->next = new ListNode(2);
32 h->next->next->next = new ListNode(3);
33 h->next->next->next->next = new ListNode(3);
34
35 Solution sol;
36 ListNode* res = sol.deleteDuplicates(h);
37
38 cout << "Optimal Deduplicated: ";
39 for (ListNode* c = res; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
40 cout << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(N) — Each step either advances curr or deletes a duplicate node. Exactly N pointer visits. Strict O(N) runtime.
  • Space complexity: O(1) — Operates strictly in-place with O(1) auxiliary pointers.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Hash Set of Seen ValuesO(N)O(N)Traverse the list while inserting seen values into a Hash Set. If the next node's value is already in the set, bypass it.Memory allocation for hash set.
2.Better — Recursive DeduplicationO(N)O(N) call stackRecursively deduplicate head.next. If head.val == head.next.val, return head.next; otherwise return head.Call stack frames.
3.Optimal — Single-Pass In-Place Neighbor BypassOptimalO(N)O(1)Iterate curr from head. If curr.val == curr.next.val, set curr.next = curr.next.next. Else curr = curr.next.Optimal.

Common Pitfalls & Crucial Edge Cases

Advancing `curr = curr.next` unconditionally

If [1, 1, 1], advancing curr after deleting the first duplicate leaves [1, 1].

Null pointer dereference on `curr.next`

Forgetting to check while (curr != null && curr.next != null).

Crucial Edge Cases to Validate:

  • Empty List — head = null -> returns null.
  • Single Node — head = [1] -> returns [1].
  • All Identical Nodes — head = [1, 1, 1, 1] -> reduces to single node [1].
  • No Duplicates — head = [1, 2, 3] -> traversed and returned unmodified.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the key detail: 'We do NOT advance curr when a duplicate is found so we can handle 3+ consecutive duplicates.'
  2. Mention that since head is always preserved, no dummy head sentinel is needed.
  3. Show explicit delete in C++ for clean memory management.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why should curr NOT be advanced when curr.val == curr.next.val?

2.What is the time complexity of the optimal in-place bypass algorithm?

3.Does this algorithm require a dummy head sentinel?

Back to DSA Sheet