Log inSign up
mediumLeetCodeNot Started

Remove Duplicates from Sorted List II

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 nodes that have duplicate numbers, leaving only distinct numbers from the original list*. Return the *linked list sorted as well*.

Example 1 · Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
Explanation: Nodes 3 and 4 appear multiple times and are completely excised, leaving only [1, 2, 5].

Example 2 · Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]
Explanation: Node 1 appears three times and is completely deleted, leaving [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:

  • Differentiate between retaining 1 copy (Part I) vs completely excising duplicates (Part II).
  • Employ the Dummy Head Sentinel pattern to handle deletions at the beginning of a list.
  • Manage moving predecessor (prev) pointers during contiguous multi-node deletions.

Pattern Recognition Trigger

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

Signals to Look For:

  • Complete elimination of any numbers that appear more than once in a sorted linked list.
  • Head node itself might be deleted.
  • Preserving sorted order in O(1) extra space.

Algorithmic Decision Tree:

  • Use dummy sentinel node initialized with dummy.next = head.
  • Only advance prev when curr has NO duplicates; if duplicates were found, update prev.next but keep prev anchored in place.

Connected Patterns:

Remove Duplicates from Sorted List IRemove Linked List ElementsPartition List

1. Brute Force — Frequency Hash Map & List Reconstruction

Intuition

Count the frequency of each value in a hash map. Build a new linked list containing only values with frequency == 1.

Algorithm

  1. Step 1: Traverse list and populate frequency map freq[node.val]++.
  2. Step 2: Create dummy = new ListNode(0) and tail = dummy.
  3. Step 3: Traverse list again: if freq[node.val] == 1, create new node and append to tail.
  4. Step 4: Return dummy.next.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_map>
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 unordered_map<int, int> freq;
16 for (ListNode* c = head; c; c = c->next) freq[c->val]++;
17
18 ListNode* dummy = new ListNode(0);
19 ListNode* tail = dummy;
20
21 for (ListNode* c = head; c; c = c->next) {
22 if (freq[c->val] == 1) {
23 tail->next = new ListNode(c->val);
24 tail = tail->next;
25 }
26 }
27 ListNode* res = dummy->next;
28 delete dummy;
29 return res;
30 }
31};
32
33int main() {
34 ListNode* h = new ListNode(1);
35 h->next = new ListNode(2);
36 h->next->next = new ListNode(3);
37 h->next->next->next = new ListNode(3);
38 h->next->next->next->next = new ListNode(4);
39 h->next->next->next->next->next = new ListNode(4);
40 h->next->next->next->next->next->next = new ListNode(5);
41
42 Solution sol;
43 ListNode* res = sol.deleteDuplicates(h);
44
45 cout << "Brute Force Deduplicated II: ";
46 for (ListNode* c = res; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
47 cout << endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(N) — Pass 1 counts frequencies in O(N). Pass 2 constructs new list of unique elements in O(N).
  • Space complexity: O(N) — Allocates a hash map of unique values and new nodes.

Why Brute Force Doesn't Scale:

Hash maps use O(N) extra space and cause memory fragmentation.

For N = 100,000 nodes, in-place lookahead bypass completes in <0.6ms.

2. Better — Recursive Duplicate Elimination

Intuition

If head.val == head.next.val, loop past all consecutive nodes with that value and return deleteDuplicates(curr.next) (skipping head entirely). If head.val != head.next.val, recursively set head.next = deleteDuplicates(head.next) and return head.

Algorithm

  1. Step 1: If head == null || head.next == null, return head.
  2. Step 2: If head.val == head.next.val:
  3. a. Advance head = head.next while head.next != null && head.val == head.next.val.
  4. b. Return deleteDuplicates(head.next) (skips entire duplicate run).
  5. Step 3: Else:
  6. a. Set head.next = deleteDuplicates(head.next).
  7. b. 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
16 if (head->val == head->next->val) {
17 while (head->next && head->val == head->next->val) {
18 head = head->next;
19 }
20 return deleteDuplicates(head->next);
21 } else {
22 head->next = deleteDuplicates(head->next);
23 return head;
24 }
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
34 Solution sol;
35 ListNode* res = sol.deleteDuplicates(h);
36
37 cout << "Recursive Deduplicated II: ";
38 for (ListNode* c = res; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
39 cout << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(N) — Each node is visited once during recursive descent. Call stack depth is N.
  • Space complexity: O(N) call stack — Recursive call stack requires O(N) memory.

3. Optimal — Sentinel Dummy Head with Lookahead Run Bypass

Intuition

Initialize dummy = new ListNode(0, head) and prev = dummy. When head.next != null && head.val == head.next.val, fast-forward head until head.next == null || head.val != head.next.val, then connect prev.next = head.next (bypassing the entire duplicate block). If no duplicate, advance prev = prev.next. Finally advance head = head.next.

Algorithm

  1. Step 1: Create dummy = new ListNode(0, head), prev = dummy.
  2. Step 2: While head != null:
  3. a. If head.next != null && head.val == head.next.val:
  4. - While head.next != null && head.val == head.next.val: advance head = head.next.
  5. - prev.next = head.next (bypass all duplicates).
  6. b. Else: advance prev = prev.next.
  7. c. Advance head = head.next.
  8. Step 3: Return dummy.next.

Remove Duplicates II Master Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Prefix [1, 2] verified
Visual state
Values and pointers at this exact step
linked list
prev → 2
Node 1
1
Node 2
2
NULL
Check / comparison
No duplicates for 1, 2
Decision / next transition
Keep nodes
Why this step matters

Prefix [1, 2] verified.

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 ListNode(int x, ListNode* n) : val(x), next(n) {}
10};
11
12class Solution {
13public:
14 ListNode* deleteDuplicates(ListNode* head) {
15 ListNode dummy(0, head);
16 ListNode* prev = &dummy;
17
18 while (head) {
19 if (head->next && head->val == head->next->val) {
20 while (head->next && head->val == head->next->val) {
21 head = head->next;
22 }
23 prev->next = head->next;
24 } else {
25 prev = prev->next;
26 }
27 head = head->next;
28 }
29
30 return dummy.next;
31 }
32};
33
34int main() {
35 ListNode* h = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(3, new ListNode(4, new ListNode(4, new ListNode(5)))))));
36
37 Solution sol;
38 ListNode* res = sol.deleteDuplicates(h);
39
40 cout << "Optimal Deduplicated II: ";
41 for (ListNode* c = res; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
42 cout << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N) — Visits each node at most twice (once for lookahead, once for deletion). Strictly O(N) linear time.
  • Space complexity: O(1) — Uses a single dummy sentinel node and 2 pointers (prev, curr) with strictly O(1) auxiliary space.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Frequency Hash Map & List ReconstructionO(N)O(N)Count frequencies of all node values in a Hash Map. Traverse the list in a second pass and keep only nodes whose frequency is exactly 1.Memory allocation for hash map.
2.Better — Recursive Sublist DeduplicationO(N)O(N) call stackIf head.val == head.next.val, skip all nodes with head.val and recursively return deleteDuplicates(curr.next). Else set head.next = deleteDuplicates(head.next) and return head.Call stack frames.
3.Optimal — Sentinel Dummy Head with Lookahead Run BypassOptimalO(N)O(1)Maintain dummy sentinel. Traverse with prev and curr. When curr.val == curr.next.val, advance curr through the duplicate run and wire prev.next = curr.next. If unique, advance prev = prev.next.Optimal.

Common Pitfalls & Crucial Edge Cases

Advancing `prev` after duplicate excision

Advancing prev when duplicates are removed can connect to another duplicate run incorrectly.

Not using a dummy sentinel

If the first few nodes are duplicates, head changes; without a dummy node, tracking the new head is prone to bugs.

Crucial Edge Cases to Validate:

  • All Nodes Duplicate — head = [1, 1, 2, 2] -> returns null.
  • Duplicates at Head — head = [1, 1, 1, 2] -> returns [2].
  • Duplicates at Tail — head = [1, 2, 3, 3] -> returns [1, 2].
  • No Duplicates — head = [1, 2, 3] -> returns [1, 2, 3].

Interview Tips & Best Practices

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

  1. Highlight the difference from Part I immediately: 'In Part II, we delete ALL occurrences of duplicates, so the head itself might be deleted.'
  2. Explain why a dummy head sentinel is used.
  3. Trace the prev pointer rule: 'prev only moves forward when no duplicate was found.'

Quick Comprehension Check

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

1.Why is a dummy sentinel node mandatory for Remove Duplicates II?

2.When should prev be advanced to prev.next?

3.What is the time complexity of the optimal lookahead solution?

Back to DSA Sheet