Remove Duplicates from Sorted List II
Problem Description
Question
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,3,3,4,4,5]
1
3
3
4
4
5
null
Output:[1,5]
1
5
null
Example 2:
Input:head=[1,1,1,2,3]
1
1
1
2
3
null
Output:[2,3]
2
3
null
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.
Solve it on LeetCode
Approaches
1. Two Pointers with Dummy Node
Intuition:
In this problem, we are dealing with a sorted linked list. The goal is to remove all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
- The sorted nature of the list allows us to detect duplicates by simply comparing adjacent nodes.
- To handle edge cases, like a head that needs to be removed because it's duplicated, we can use a dummy node. A dummy node is a temporary node that helps simplify edge case handling, such as head deletion.
- By using two pointers,
prevandcurrent, we can manage list traversal and modification efficiently.
Steps:
- Initialize a dummy node that points to the head of the linked list.
- Use a pointer
prevto track the last node before the sequence of duplicates. - Use another pointer
currentto iterate through the list. - For each node, compare it with the next node to check if it's a start of a duplicate sequence.
- When a series of duplicates is detected,
prev’s next is linked to the node after the duplicates. - If no duplicates are found, simply move
prevtocurrent. - Continue this process until the end of the list.
- Finally, return
dummy.nextbecausedummywas pointing to the beginning of the list structure we have built.
Code:
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the list. We traverse the list once.
- Space Complexity: O(1), because we only use a fixed amount of extra space (pointers).