Remove Duplicates from Sorted List II - Solution & Explanation
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:
Input: head = [1,2,3,3,4,4,5] Output: [1,2,5]
Example 2:
Input: head = [1,1,1,2,3] Output: [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.
Approach Overview
Problem Overview: You are given a sorted linked list. If a value appears more than once, every node with that value must be removed. Only values that appear exactly once should remain in the final list.
Approach 1: Iterative Approach using Two Pointers (O(n) time, O(1) space)
The list is sorted, so duplicates always appear in consecutive nodes. Use two pointers to scan the list: a prev pointer tracking the last confirmed unique node and a curr pointer that scans forward. When curr encounters duplicates (multiple nodes with the same value), advance it until the value changes, then link prev.next to the first different node. A dummy head simplifies edge cases when duplicates appear at the beginning. This approach performs a single linear traversal and modifies pointers in-place, making it the most efficient solution.
This method relies on properties of a linked list and sequential traversal using a two pointers pattern. Because the list is sorted, you never need extra memory to track frequencies. Each node is visited once, giving O(n) time and O(1) auxiliary space.
Approach 2: Recursive Approach (O(n) time, O(n) space)
The recursive solution processes the list from the head and decides whether the current node should remain. If the next node has the same value, all nodes with that value must be skipped. Recursively move forward until a different value appears, then continue processing the remainder of the list. If the current value is unique, connect the node to the result of the recursive call on the next node.
This approach mirrors the problem definition closely and leads to concise code. However, recursion adds call stack overhead. In the worst case (a list with all unique values), recursion depth reaches n, giving O(n) extra space.
Recommended for interviews: The iterative two-pointer approach is what most interviewers expect. It demonstrates strong understanding of linked list pointer manipulation and efficient in-place processing. The recursive solution is elegant and useful for reasoning about the problem, but interviewers typically prefer the iterative O(1) space implementation.
Approach 1: Iterative Approach using Two Pointers
In this approach, we'll use two pointers: prev and current. The prev pointer will be the last node in the result list without duplicates, and current pointer will traverse the input list. We initialize a dummy node before the head to simplify the edge case management when duplicates are at the start of the list.
While traversing, if the current node has the same value as the next node, we keep moving forward to skip all nodes with this value. If prev.next points to the current node when a duplicate sequence starts, we simply remove the sequence by connecting prev to the node after the last duplicate.
The C solution defines a ListNode structure to represent each node in the linked list. A dummy node is initialized with dummy.next pointing to head. Two pointers, prev and current, are used to traverse and modify the linked list to remove duplicates. The while loop ensures that all duplicates are detected and skipped over, while prev is maintained to ensure only distinct numbers are retained in the list.
Complexity
Time Complexity: O(n), where n is the number of nodes in the list, because each node is visited at most twice.
Space Complexity: O(1), as no additional space is used aside from a few pointers.
Approach 2: Recursive Approach
This approach utilizes recursion to elegantly process the list for duplicates. The concept centers on calling a helper function that, at each level, processes the current node list by recursively evaluating burdens of duplicates. The recursion simplifies decision-making by naturally moving through the list and sorting out duplicate removal due to stack calls automatically handling execution follow-through.
Each call checks for duplicate patterns and recursively bridges connections between unique nodes. This allows the call stack to effectively tackle the transformation demands of duplicate filtering through returning modified structures created per recursion.
The Python recursive solution systematically checks each node and its successively linked node's equality. When duplicates are found, the head progress skips them altogether, recursively pursuing a clean node linkage post-duplicate skipping.
Code
Python
Complexity
Time Complexity: O(n), visiting each node once recursively.
Space Complexity: O(n), accounting for call stack space in recursion.
Approach 3: Single Pass
First, we create a dummy head node dummy, and set dummy.next = head. Then we create a pointer pre pointing to dummy, and a pointer cur pointing to head, and start traversing the linked list.
When the node value pointed by cur is the same as the node value pointed by cur.next, we let cur keep moving forward until the node value pointed by cur is different from the node value pointed by cur.next. At this point, we check whether pre.next is equal to cur. If they are equal, it means there are no duplicate nodes between pre and cur, so we move pre to the position of cur; otherwise, it means there are duplicate nodes between pre and cur, so we set pre.next to cur.next. Then we continue to move cur forward. Continue the above operation until cur is null, and the traversal ends.
Finally, return dummy.next.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the linked list.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| Approach | Complexity |
|---|---|
| Iterative Approach using Two Pointers | Time Complexity: O(n), where n is the number of nodes in the list, because each node is visited at most twice. |
| Recursive Approach | Time Complexity: O(n), visiting each node once recursively. |
| Single Pass | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Two Pointers | O(n) | O(1) | Best choice for interviews and production since it removes duplicates in-place with constant memory |
| Recursive Approach | O(n) | O(n) | Useful for conceptual clarity or when recursive list processing is preferred |
Video Solution
Remove Duplicates from Sorted List II | Live Coding with Explanation | Leetcode - 82 • Algorithms Made Easy • 57,271 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Remove Duplicates from Sorted List II easy or hard?
How to solve Remove Duplicates from Sorted List II in O(n)?
Remove Duplicates from Sorted List II Python or Java solution?
What is the best approach for Remove Duplicates from Sorted List II?
What data structure is used in Remove Duplicates from Sorted List II?
What is the time complexity of Remove Duplicates from Sorted List II?
Is Remove Duplicates from Sorted List II asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Remove Duplicates from Sorted List II with our built-in code editor and test cases.
Practice on FleetCode