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:
[0, 300].-100 <= Node.val <= 100Problem Overview: Given the head of a sorted linked list, remove every value that appears more than once so that only distinct numbers remain. Unlike the simpler duplicate-removal problem, nodes that repeat must be removed entirely rather than keeping one occurrence.
This constraint changes the strategy. Instead of skipping extra duplicates, you must detect a duplicate run and remove the whole sequence from the list.
Approach 1: Iterative Two Pointers (O(n) time, O(1) space)
The most common solution uses pointer manipulation with a sentinel (dummy) node and two pointers. A prev pointer tracks the last confirmed unique node, while curr scans the list. When curr and curr.next have the same value, you’ve found the start of a duplicate block. Continue advancing curr until the value changes, then connect prev.next directly to the first non-duplicate node.
The key insight: because the list is sorted, duplicates always appear consecutively. That means you only need a single linear scan to detect and skip them. The dummy node handles edge cases where duplicates occur at the beginning of the list. This solution runs in O(n) time because each node is visited once, and uses O(1) extra space since it modifies pointers in-place. This approach relies heavily on understanding linked list pointer manipulation and a classic two pointers traversal pattern.
Approach 2: Recursive Approach (O(n) time, O(n) space)
The recursive solution processes the list from the head while deciding whether to keep or discard nodes. If the current node has the same value as the next node, it means a duplicate sequence begins. Skip all nodes with that value, then recursively process the remainder of the list and return that result as the new head.
If the current node is unique (its value differs from the next node), keep it and recursively process head.next. Attach the returned list to head.next. The recursion naturally rebuilds the filtered list while skipping duplicates. This approach also runs in O(n) time, but requires O(n) space for the recursion stack. It’s conceptually clean but less memory-efficient than the iterative pointer solution.
Recommended for interviews: The iterative dummy-node + two-pointer technique is the expected solution. It demonstrates control over pointer updates and careful handling of edge cases such as duplicates at the head or entire list removal. Mentioning the recursive variant shows deeper understanding, but the O(1) space iterative approach is what most interviewers prefer for problems involving linked lists.
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.
C++
Java
Python
C#
JavaScript
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.
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.
Time Complexity: O(n), visiting each node once recursively.
Space Complexity: O(n), accounting for call stack space in recursion.
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Two Pointers with Dummy Node | O(n) | O(1) | Best general solution when modifying the list in-place with minimal memory |
| Recursive Linked List Processing | O(n) | O(n) | Useful for cleaner logic when recursion is acceptable and stack space is not a concern |
Remove Duplicates from Sorted Array II - Leetcode 80 - Python • NeetCodeIO • 88,711 views views
Watch 9 more video solutions →Practice Remove Duplicates from Sorted List II with our built-in code editor and test cases.
Practice on FleetCode