Remove Duplicates From Sorted List Solution for Capgemini
Company: Capgemini · Difficulty: Easy · Topics: Linked List, Two Pointers
Problem Statement
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
Examples
Example 1:
Input: head = [1,1,2]
Output: [1,2]
Explanation: The linked list becomes 1->2 after removing duplicates.
Example 2:
Input: head = [1,1,2,3,3]
Output: [1,2,3]
Explanation: The linked list becomes 1->2->3 after removing duplicates.
Example 3:
Input: head = [1,1,1]
Output: [1]
Explanation: The linked list becomes 1 after removing all duplicates.
Intuition
Since the linked list is already sorted, duplicates will always be adjacent. We can use a single pointer to traverse the list and remove duplicates by adjusting the next pointers.
The key insight is:
1. If current node's value equals next node's value, skip the next node
2. If they are different, move to the next node
3. Continue until we reach the end of the list
Approach
Approach 1: Single Pointer (Optimal)
1. Start with current pointer at head
2. While current and current->next are not null:
- If current->val == current->next->val, skip the next node
- Else, move current to next node
3. Return the modified list
Approach 2: Two Pointers
1. Use prev and curr pointers
2. If curr->val == curr->next->val, update prev->next to skip curr->next
3. Else, move both pointers forward
Approach 3: Recursive Approach
1. Base case: if head is null or head->next is null, return head
2. If head->val == head->next->val, return recursive call on head->next
3. Else, head->next = recursive call on head->next, return head
Dry Run
Let's trace through Example 1: head = [1,1,2]
Single Pointer Approach:
- Initial: current = 1, list = 1->1->2
- current->val (1) == current->next->val (1): skip next node
- current->next = current->next->next: list = 1->2
- current = current->next: current = 2
- current->next is null: stop
- Result: 1->2
Example 2: head = [1,1,2,3,3]
- Initial: current = 1, list = 1->1->2->3->3
- current->val (1) == current->next->val (1): skip next node
- list = 1->2->3->3
- current = current->next: current = 2
- current->val (2) != current->next->val (3): move to next
- current = current->next: current = 3
- current->val (3) == current->next->val (3): skip next node
- list = 1->2->3
- current->next is null: stop
- Result: 1->2->3
Key Insights
1. Sorted Property: Since list is sorted, duplicates are always adjacent
2. In-place Modification: We modify the list structure by adjusting pointers
3. Single Pass: Only one traversal is needed
4. Memory Efficient: No extra space required
Edge Cases
1. Empty list: Return null
2. Single node: Return the node as is
3. All duplicates: Return single node
4. No duplicates: Return list as is
5. Duplicates at end: Handle properly by stopping at null
Time and Space Complexity
- Time Complexity: O(n) - we visit each node at most once
- Space Complexity: O(1) - we only use a constant amount of extra space