Loading problems...
TL;DR: The optimal solution uses a sentinel node and a predecessor pointer to detect sequences of duplicates and rewire the next pointers to skip them entirely, ensuring O(N) time and O(1) space.
In the Remove Duplicates from Sorted List II problem, we are provided with the head of a sorted linked list. Our objective is to traverse the list and delete all nodes that have duplicate numbers. Unlike the simpler version (LeetCode 83) where we keep one instance of each number, here we must remove all nodes belonging to a duplicate set, leaving only distinct numbers. The result must remain sorted.
This is a popular interview question that tests your ability to manage pointers precisely without losing track of the list's structure. The LeetCode 82 solution requires careful handling of edge cases, particularly when the head of the list itself needs to be removed.
The brute force approach typically involves using auxiliary data structures to track the frequency of every value in the linked list before rebuilding it.
Naive Algorithm:
1, append a new node with that value to the result list.Why it fails (or is suboptimal): While this approach produces the correct output, it fails to meet the efficiency standards of a senior-level interview.
The core insight relies on the fact that the input list is sorted. This guarantees that all duplicates of a specific value are grouped together contiguously. We do not need a global frequency count; we only need to look at the immediate neighborhood of the current node.
To solve this in-place, we utilize the pointer manipulation techniques found in reversal algorithms. Specifically, we maintain a prev pointer that acts as an anchor. As we scan forward with curr, if we detect a sequence of duplicates, we do not advance prev. Instead, we fast-forward curr past the duplicates and then strictly rewire prev.next to point to the new curr. This effectively excises the sub-segment of duplicates.
This requires a Sentinel Node (Dummy Head). Since the head of the list itself might be a duplicate (e.g., 1 -> 1 -> 2), it might need to be removed. A sentinel node ensures that head is never a special case; prev can always start at the sentinel.
Visual Description:
Imagine the list as a chain. We hold the link before a potential duplicate group (prev). We send a scout (head or curr) forward. If the scout sees identical values ahead, it keeps running until the values change. Once the scout lands on a distinct value (or null), we disconnect the chain at prev and snap it directly to the scout's new position, dropping the entire segment of duplicates into garbage collection.

Let's trace the algorithm with Input: 1 -> 2 -> 3 -> 3 -> 4.
Setup:
sentinel -> 1 -> 2 -> 3 -> 3 -> 4prev points to sentinel.head points to 1.Iteration 1 (head = 1):
head.val (1) vs head.next.val (2). Different.1 is distinct.prev to 1.head to 2.Iteration 2 (head = 2):
head.val (2) vs head.next.val (3). Different.2 is distinct.prev to 2.head to 3.Iteration 3 (head = 3):
head.val (3) vs head.next.val (3). Duplicate detected.head.next exists and equals 3, move head.head moves to the second 3.head.next is 4 (distinct).prev.next (currently node 2's next) to head.next (node 4).2 -> 3 -> 3 is broken. It is now 2 -> 4.head to .Iteration 4 (head = 4):
head.val (4) vs head.next (null). No duplicate.prev to 4.head to null.Termination:
head is null. Loop ends.sentinel.next (1 -> 2 -> 4).The algorithm's correctness relies on the sorted invariant. Because the list is sorted, duplicates are strictly adjacent. By checking head.val == head.next.val, we can greedily identify the start of a duplicate sequence. By advancing head until the values differ, we identify the end of that sequence.
The usage of the sentinel node guarantees that we can always perform the prev.next = ... operation, even if the entire list consists of duplicates (resulting in an empty list) or if the head is removed. The logic ensures prev is only advanced when a node is confirmed unique, maintaining the integrity of the result list.
cpp/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (!head || !head->next) return head; // Sentinel node to handle edge cases where head is deleted ListNode* sentinel = new ListNode(0, head); ListNode* prev = sentinel; while (head) { // If current node is a duplicate if (head->next && head->val == head->next->val) { // Move head until the end of the duplicates while (head->next && head->val == head->next->val) { head = head->next; } // Skip all duplicates prev->next = head->next; } else { // No duplicate, move prev forward prev = prev->next; } // Move head to the next node to process head = head->next; } ListNode* result = sentinel->next; delete sentinel; // Cleanup memory return result; } };
java/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null) return null; // Sentinel node prevents loss of head reference ListNode sentinel = new ListNode(0, head); ListNode prev = sentinel; while (head != null) { // Check if current node is the start of duplicates if (head.next != null && head.val == head.next.val) { // Loop until the last node of the duplicate sequence while (head.next != null && head.val == head.next.val) { head = head.next; } // Rewire prev to skip the duplicates entirely prev.next = head.next; } else { // If distinct, prev can safely advance prev = prev.next; } // Move head forward to continue scanning head = head.next; } return sentinel.next; } }
python# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: # Sentinel node handles the case where the head itself is a duplicate sentinel = ListNode(0, head) prev = sentinel while head: # Check if we have a duplicate sequence if head.next and head.val == head.next.val: # Move head until we reach the last node of the duplicate set while head.next and head.val == head.next.val: head = head.next # Wire prev to the node AFTER the duplicates prev.next = head.next else: # Current node is distinct, move prev forward prev = prev.next # Move head forward for the next iteration head = head.next return sentinel.next
Time Complexity: O(N)
We traverse the linked list exactly once. Although there is a nested movement of the head pointer to skip duplicates, each node is visited and processed a constant number of times (once by the main loop or once by the skip logic).
Space Complexity: O(1)
We only use a finite number of pointers (sentinel, prev, head) regardless of the input size. We modify the list structure in-place without allocating new nodes.
The logic used in LeetCode 82 is a fundamental application of Linked List Manipulation Patterns. You will find similar pointer mechanics in:
prev and curr to rewire a sub-segment).Mastering the precise movement of prev and curr here is crucial for solving these harder reversal problems.
Why do I get a Null Pointer Exception?
head.next.val without checking if head.next is null.head and head.next exist before accessing their values.Why is my output missing the distinct head?
1, 1, 2), logic that relies on head being valid initially will fail to delete the first group.4prev did NOT move. It stays at 2.headsentinel.nextWhy are duplicates still present in the output?
prev inside the duplicate handling logic.prev when you are certain the current node is distinct. If you detect duplicates, prev must stay put so it can link to the next distinct node found later.Why does the solution Time Limit Exceeded (TLE)?
head correctly inside the inner while loop.head towards null or a new value.