Question: Write code to remove duplicates from an unsorted linked list.if temporary buffer is not allowed.
Solution:
In order to solve this problem we can use Hashtable but will not solve our purpose.Lets do it first by Hashtable then will do more optimize solution for it.
public static void deleteDuplicate(LinkedListNode n)
{
Hashtable table=new Hashtable();
LinkedListNode prev=null;
while(n!=null)
{
if(table.containsKey(n.data))
{
prev.next= n.next;
}
else
{
table.put(n.data,true);
prev=n;
}
n=n.next;
}
}
The above solution takes o(N) time
N=number of elements in the linked-list.
No Buffer Allowed Solution:
public static void deleteDups(LinkedListNode head)
{
if(head == null)
return;
LinkedListNode current= head;
while(current!=null)
{
LinkedListNode runer=current;
while(runer.next != null)
{
if(runer.next.data == current.data)
{
runer.next=runer.next.next;
}
else
{
runer =runer.next;
}
}
current =current.next;
}
}
Complexity is o(1) space but o(n^2) time.