Remove duplicates from an unsorted linked list

Question

import java.util.*;
/*
 *  Remove duplicates from an unsorted linked list
 */
public class LinkedListNode {  
    public int data;  
    public LinkedListNode next;  

    public LinkedListNode(int data) {  
        this.data = data;    
    }  
}

public class Task {
    public static void deleteDups(LinkedListNode head){
      Hashtable<Integer, Boolean> table=new Hashtable<Integer, Boolean>();
      LinkedListNode previous=null;
      //nth node is not null
      while(head!=null){
        //have duplicate
            if(table.containsKey(head.data)){
                            //skip duplicate
                previous.next=head.next;
            }else{
            //put the element into hashtable
            table.put(head.data,true);
            //move to the next element
            previous=head;
            }
      //iterate
      head=head.next;
      }
   }
   public static void main (String args[]){
       LinkedList<Integer> list=new LinkedList<Integer>();
       list.addLast(1);
       list.addLast(2);
       list.addLast(3);
       list.addLast(3);
       list.addLast(3);
       list.addLast(4);
       list.addLast(4);
       System.out.println(list);
       LinkedListNode head=new LinkedListNode(list.getFirst());
       Task.deleteDups(head);
       System.out.println(list);
   }
}

The result: [1, 2, 3, 3, 3, 4, 4] [1, 2, 3, 3, 3, 4, 4]

It does not eliminate the duplicates.

Why doesn't the method work?

Answer 1

Iterate through the linked list, adding each element to a hash table. When we discover a duplicate element, we remove the element and continue iterating. We can do this all in one pass since we are using a linked list.

The following solution takes O(n) time, n is the number of element in the linked list.

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;
  }
}

Answer 2

The first problem is that

LinkedListNode head=new LinkedListNode(list.getFirst());

does not actually initialize head with the contents of list. list.getFirst() simply returns the Integer 1, and head contains 1 as its only element. You would have to initialize head by looping through list in order to get all of the elements.

In addition, although

Task.deleteDups(head)

modifies head, this leaves list completely unchanged—there is no reason why the changes to head should propagate to list. Therefore, to check your method, you would have to loop down head and print out each element, rather than printing out list again.

Answer 3

/**
*
* Remove duplicates from an unsorted linked list.
*/
public class RemoveDuplicates {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<String>();
        list.add("Apple");
        list.add("Grape");
        list.add("Apple");
        HashSet<String> set = removeDuplicatesFromList(list);
        System.out.println("Removed duplicates" + set);
    }
    public static HashSet<String> removeDuplicatesFromList(LinkedList<String> list){
        HashSet<String> set = new LinkedHashSet<String>();
        set.addAll(list);
        return set;
    }
}

Answer 4

All the solutions given above looks optimised but most of them defines custom Node as a part of solution. Here is a simple and practical solution using Java's LinkedList and HashSet which does not confine to use the preexisting libraries and methods.

Time Complexity : O(n)

Space Complexity: O(n)

@SuppressWarnings({ "unchecked", "rawtypes" })
private static LinkedList<?> removeDupsUsingHashSet(LinkedList<?> list) {

    HashSet set = new HashSet<>();
    for (int i = 0; i < list.size();) {
        if (set.contains(list.get(i))) {
            list.remove(i);
            continue;
        } else {
            set.add(list.get(i));
            i++;
        }
    }
    return list;
}

This also preserves the list order.

Answer 5

It's simple way without HashSet or creation Node.

public String removeDuplicates(String str) {
    LinkedList<Character> chars = new LinkedList<Character>();

    for(Character c: str.toCharArray()){
        chars.add(c);
    }

    for (int i = 0; i < chars.size(); i++){
        for (int j = i+1; j < chars.size(); j++){
            if(chars.get(j) == chars.get(i)){
                chars.remove(j);
                j--;
            }
        }
    }

    return new String(chars.toString());
}

And to verify it:

@Test
public void verifyThatNoDuplicatesInLinkedList(){
    CodeDataStructures dataStructures = new CodeDataStructures();

    assertEquals("abcdefghjk", dataStructures.removeDuplicates("abcdefgabcdeaaaaaaaaafabcdeabcdefgabcdbbbbbbefabcdefghjkabcdefghjkghjkhjkabcdefghabcdefghjkjfghjkabcdefghjkghjkhjkabcdefghabcdefghjkj")
            .replace(",", "")
            .replace("]", "")
            .replace("[", "")
            .replace(" ", ""));
}

Answer 6

1. The solution you have provided does not modify the original list.
2. To modify the original list and remove duplicates, we can iterate with two pointers. Current: which iterates through LinkedList, and runner which checks all subsequent nodes for duplicates.

3. The code below runs in O(1) space but O(N square) time.

   public void deleteDups(LinkedListNode head){

   if(head == null)
       return;
   
   LinkedListNode currentNode = head;       
   while(currentNode!=null){
       LinkedListNode runner = currentNode;
       while(runner.next!=null){
           if(runner.next.data == currentNode.data)
               runner.next = runner.next.next;
           else
               runner = runner.next;
       }
       currentNode = currentNode.next;
   }
   

   }

Reference : Gayle laakmann mcdowell