1. Problem Statement (Simple Explanation)
You’re given the head of a sorted singly linked list.
You must delete all nodes that have duplicate values, so that only values that appear exactly once in the original list remain.
Return the head of the resulting list (still sorted).
Important:
If a value appears more than once, remove all occurrences of that value.
The list is sorted ascending, so duplicates are in contiguous blocks.
2. Examples
Example 1:
Input: head = [1,2,3,3,4,4,5]
Values:
1 → appears once → keep
2 → appears once → keep
3 → appears twice → remove both 3s
4 → appears twice → remove both 4s
5 → appears once → keep
Output: [1,2,5]
Example 2:
Input: head = [1,1,1,2,3]
Values:
1 → appears three times → remove all 1s
2 → keep
3 → keep
Output: [2,3]
3. Approach – One Pass with Dummy Head (O(n), O(1))
Because the list is sorted, duplicates are grouped together.
We want to remove whole groups where the value appears more than once.
We’ll use:
A dummy head node pointing to head to simplify deletions at the front.
A pointer prev that always points to the last node of the cleaned list (the last node we know should be kept).
A pointer curr that scans through the list.
Algorithm:
Create dummy with dummy.next = head.
Set prev = dummy, curr = head.
While curr != null:
Check if curr is the start of a duplicate block:
If curr.next != null and curr.val == curr.next.val, we have duplicates.
Remember dupVal = curr.val.
Move curr forward while curr != null and curr.val == dupVal (skip all nodes with this value).
Then connect: prev.next = curr → removes the entire block.
Else (no duplicate starting at curr):
The curr node is unique so far, so:
Move prev = curr
Move curr = curr.next
At the end, return dummy.next.
Pseudo-code:
Time: O(n) – each node is visited at most twice.
Space: O(1) extra – in-place modifications.
4. Java code
5. C code
6. C++ code
7. Python code
8. JavaScript code
Comments
Post a Comment