712264. Remove duplicates from a sorted doubly linked list
Here is a detailed Markdown blog post for the problem "Remove duplicates from a sorted doubly linked list":
Remove Duplicates from a Sorted Doubly Linked List
Summary
Given a sorted doubly linked list, remove all duplicate elements while preserving the original order. This problem requires a combination of understanding linked lists and implementing an efficient algorithm to eliminate duplicates.
Detailed Explanation
The problem can be solved by iterating through the linked list, comparing each node with its next node (if it exists), and removing any duplicate nodes. Since the list is sorted, we only need to check if the current node's value matches the previous node's value. If they match, remove the current node; otherwise, move on to the next node.
Here is a step-by-step breakdown of the solution:
- Initialize two pointers:
prevandcurr, both pointing to the head of the list. - Iterate through the list using
curr. For each node:- Check if
curris not null (i.e., we have reached the end of the list). - If
curris not null, compare its value withprev's value. - If they match, remove
currfrom the list and move on to the next node by updatingprevandcurr.
- Check if
- Continue iterating until we reach the end of the list.
Time complexity: O(n), where n is the number of nodes in the linked list. Space complexity: O(1), as we only use a constant amount of space to store the two pointers.
Optimized Solutions
Java
public static Node removeDuplicates(Node head) {
if (head == null) return null;
Node prev = head;
Node curr = head.next;
while (curr != null) {
if (prev.val == curr.val) {
prev.next = curr.next;
curr = curr.next;
} else {
prev = curr;
curr = curr.next;
}
}
return head;
}