700125. Remove duplicates from an unsorted linked list
Easy
Remove Duplicates from an Unsorted Linked List
Slug: remove-duplicates-from-an-unsorted-linked-list
Difficulty: Easy
Id: 700125
Topic Tags: Linked List, Data Structures
Company Tags: Amazon, Intuit
Summary
Remove duplicates from an unsorted linked list is a fundamental problem in data structures. Given a singly linked list where elements can be repeated, the task is to remove all duplicate nodes and return the modified linked list.
Detailed Explanation
The problem can be solved by traversing the linked list and comparing each node with the previous one. If a node's value matches the previous one, skip it; otherwise, add it to the result list.
Here's a step-by-step breakdown of the solution:
- Initialize three pointers:
curr,prev, andresult.currwill point to the current node in the linked list,prevwill keep track of the previous node, andresultwill be the new head of the modified linked list. - Iterate through the linked list using
curr. - For each node, check if its value is different from the previous one (i.e.,
prev->data != curr->data). If it's not a duplicate, add it to the result list by updatingresultandprev. - Move
currandprevto the next nodes until the end of the linked list. - Return the modified linked list.
The time complexity is O(n), where n is the number of nodes in the linked list, as we visit each node once. The space complexity is O(1) because we only use a few extra pointers and variables.
Optimized Solutions
Java
public class Solution {
public ListNode removeDuplicates(ListNode head) {
if (head == null) return null;
ListNode curr = head, prev = head;
while (curr != null && curr.next != null) {
if (curr.data != curr.next.data) {
prev = curr;
curr = curr.next;
} else {
curr = curr.next;
}
}
return head;
}
}