Remove Duplicates from Sorted List II
In this article, we will explore the problem of removing duplicates from a sorted linked list. This problem, known as “Remove Duplicates from Sorted List II,” is a common challenge faced by programmers and developers. We will provide a step-by-step solution, including a Java implementation and a detailed explanation of the logic behind it.
Understanding the Problem
The task is to remove all duplicates from a sorted linked list. If an element appears more than once, we need to remove all instances of that element, leaving only unique values. The input is a linked list where each node contains an integer value, and the output should be a linked list with duplicates removed.
For example, given the linked list: 1 → 2 → 3 → 3 → 4 → 4 → 5, the output should be: 1 → 2 → 5. Here, the values 3 and 4 are removed entirely since they appear more than once.
Approach to the Solution
To solve this problem, we will use a two-pointer technique. The first pointer will traverse the linked list while the second pointer will help us manage the connections between nodes. The main idea is to keep track of the values we encounter and remove duplicates accordingly.
Step-by-Step Breakdown
1. **Initialization**: Start by creating a dummy node that points to the head of the linked list. This helps in managing edge cases, such as when the head itself is a duplicate.
2. **Traverse the List**: Use a pointer, say `current`, to traverse the linked list. For each node, check if it has duplicates.
3. **Identify Duplicates**: If the value of the current node is the same as the next node’s value, continue moving the pointer until you find a value that is different. This will help in identifying the range of duplicates.
4. **Remove Duplicates**: Once duplicates are identified, link the previous node to the node after the last duplicate. This effectively removes all duplicates from the list.
5. **Continue Traversing**: Move the `current` pointer to the next node and repeat the process until the end of the list is reached.
Java Implementation
Here is the Java code that implements the above logic:
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
// Create a dummy node
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = dummy;
while (current.next != null) {
ListNode nextNode = current.next;
// Check for duplicates
if (nextNode.next != null && nextNode.val == nextNode.next.val) {
// Move to the last duplicate
while (nextNode.next != null && nextNode.val == nextNode.next.val) {
nextNode = nextNode.next;
}
// Remove duplicates
current.next = nextNode.next;
} else {
current = current.next; // Move to the next node
}
}
return dummy.next; // Return the new head
}
}
Code Explanation
The `ListNode` class defines the structure of a node in the linked list. The `deleteDuplicates` method takes the head of the list as input and returns the modified list.
We start by creating a dummy node that points to the head. This simplifies our logic, especially when the head needs to be removed. We then use a while loop to traverse the list. The inner loop identifies duplicates and skips them, adjusting the pointers to remove them from the list.
After processing all nodes, we return the next node of the dummy, which is the new head of the modified list.
Time Complexity
The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. We traverse the list only once, making this approach efficient.
Space Complexity
The space complexity is O(1) since we are not using any additional data structures that scale with input size. All operations are performed in-place on the linked list.
Conclusion
Removing duplicates from a sorted linked list is a common problem that can be efficiently solved using a two-pointer approach. By carefully managing the links between nodes, we can ensure that all duplicates are removed while maintaining the order of unique values.
In summary, the key steps include initializing a dummy node, traversing the list to identify duplicates, and adjusting pointers to remove them. This method is not only effective but also optimal in terms of time and space complexity.
By mastering problems like “Remove Duplicates from Sorted List II,” you enhance your problem-solving skills and prepare yourself for more advanced challenges in programming and algorithms.