Watch 10 video solutions for Remove Duplicates from Sorted List II, a medium level problem involving Linked List, Two Pointers. This walkthrough by NeetCodeIO has 88,711 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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: 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 | 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 |