700196. Remove Duplicates from a Sorted Linked List
Remove Duplicates from a Sorted Linked List
Slug: remove-duplicate-element-from-sorted-linked-list
Difficulty: Easy
Topic Tags: Linked List, Data Structures
Company Tags: Microsoft, OYO Rooms, Oracle, Visa, Adobe, Myntra
Summary
This problem involves removing duplicate elements from a sorted linked list. The key concept involved is the manipulation of a linked list, specifically to remove duplicates while maintaining the original order.
Detailed Explanation
To solve this problem, we can iterate through the linked list and compare each node's value with the previous one. If they are equal, we skip that node (remove the duplicate). If not, we move on to the next node. This approach ensures that we only keep unique elements in the linked list.
Here is a step-by-step breakdown of the solution:
- Initialize two pointers,
currandprev, to the head of the linked list. - Traverse the linked list until
currreaches the end. - For each node, compare its value with the previous node's value (
prev->data). - If they are equal, skip this node (move
currone step forward) and continue to the next iteration. - If they are not equal, update
prevto the current node and movecurrone step forward. - Repeat steps 3-5 until
currreaches the end of the linked list.
The time complexity for this solution is O(n), where n is the number of nodes in the linked list. The space complexity is O(1) because we only use a constant amount of extra space (for the two pointers).
Optimized Solutions
Java
public class RemoveDuplicates {
public static Node removeDuplicates(Node head) {
if (head == null) return null;
Node curr = head;
Node prev = head;
while (curr != null && curr.next != null) {
if (curr.data == prev.data) {
curr = curr.next;
continue;
}
prev = curr;
curr = curr.next;
}
return head;
}
}