Remove Duplicates from Unsorted List
Given the head
of a unsorted linked list, delete all duplicates such that each element appears only once. Return the linked list as well.
Solutions
Approach 1 ā Using hash table
Easy solution, use hash table to check duplicate item.
Steps
iterate through the linked list and adding each element to a hash table.
Whenwe discover a duplicate element, we remove the element and continue iterating.
Return
head
node.
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode DeleteDuplicates(ListNode head)
{
HashSet<int> set = new HashSet<int>();
ListNode previous = null;
if (head == null) return null;
ListNode temp = head;
while (temp != null)
{
if (set.Contains(temp.val))
{
previous.next = temp.next;
}
else
{
set.Add(temp.val);
previous = temp;
}
temp = temp.next;
}
return previous;
}
}
Time Complexity: O(n)
Auxiliary Space: O(n)
Approach 2 ā No Buffer Allowed
lf we don't have a buffer, we can iterate with two pointers: current which iterates through the linked list, and runner which checks all subsequent nodes for duplicates.
Steps
iterate through the linked list and adding each element to a hash table.
Whenwe discover a duplicate element, we remove the element and continue iterating.
Return
head
node.
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode DeleteDuplicates(ListNode head)
{
ListNode current = head;
while (current != null)
{
ListNode runner = current;
while (runner.next != null)
{
if (current.val == runner.next.val)
{
runner.next = runner.next.next;
}
else
{
runner = runner.next;
}
}
current = current.next;
}
return head;
}
}
Time Complexity: O(n²)
Auxiliary Space: O(1)
Last updated