Saturday , 20 September 2014
Home » Technical Interview » Remove duplicates from an unsorted linked list

Remove duplicates from an unsorted linked list

Q.) Write code to remove duplicates from an unsorted linked list

Ans) If we can use a buffer, we can keep track of elements in a hashtable and remove any dups:

public static void deleteDups(LinkedListNode n) {
  Hashtable table = new Hashtable();
  LinkedListNode previous = null;
  while (n != null) {
    if (table.containsKey(n.data)) previous.next = n.next;
    else {
      table.put(n.data, true);
      previous = n;
    }
     n = n.next;
   }
 }

Without a buffer, we can iterate with two pointers: “current” does a normal iteration, while

“runner”  iterates  through  all  prior  nodes  to  check  for  dups     Runner  will  only  see  one  dup

per node, because if there were multiple duplicates they would have been removed already

public static void deleteDups2(LinkedListNode head) {
  if (head == null) return;
  LinkedListNode previous = head;
  LinkedListNode current = previous.next;
  while (current != null) {
    LinkedListNode runner = head;
    while (runner != current) { // Check for earlier dups
      if (runner.data == current.data) {
        LinkedListNode tmp = current.next; // remove current
         previous.next = tmp; 
         current = tmp; // update current to next node
         break; // all other dups have already been removed
       }
       runner = runner.next;
     }
     if (runner == current) { // current not updated - update now
       previous = current;
       current = current.next;
     }
   }
 }

About admin

Let me first introduce myself.... Sudhir has done my Engineering in Information Technology form Lingaya's Institute of Management and Technology Faridabad, India. Sudhir has worked on VC++, MFC, COM, C++, C Sharp, ASP.NET, Sharepoint and on Latest Web 2.0 stuff Jquery, Ajax. Currently Sudhir Mangla is working as Team Leader (architect ) (Silverlight , C Sharp, ASP.NET, Sharepoint and on Latest Web 2.0 stuff Jquery, Ajax) developer in Svam International, Noida.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>