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

Here is a very easy version.

LinkedList<Integer> a = new LinkedList<Integer>(){{
  add(1);
  add(1);
}}
Set<Integer> set = new HashSet<Integer>(a);
a = new LinkedList<Integer>(set);

LinkedList<Integer> a = new LinkedList<Integer>(){{
  add(1);
  add(1);
}}
Set<Integer> set = new HashSet<Integer>(a);
a = new LinkedList<Integer>(set);

Very concise. Isn't it?

Answer 2

Below code implements this without needing any temporary buffer. It starts with comparing first and second nodes, if not a match, it adds char at first node to second node then proceeds comparing all chars in second node to char at third node and so on. After comperison is complete, before leaving the node it clears everything that is added and restores its old value which resides at node.val.char(0)

F > FO > FOL > (match found, node.next = node.next.next) > (again match, discard it) > FOLW > ....

public void onlyUnique(){
        Node node = first;
        while(node.next != null){
            for(int i = 0 ; i < node.val.length(); i++){
                if(node.val.charAt(i) == node.next.val.charAt(0)){
                    node.next = node.next.next;
                }else{
                    if(node.next.next != null){ //no need to copy everything to the last element
                        node.next.val = node.next.val + node.val;
                    }
                    node.val = node.val.charAt(0)+ "";
                }
            }
            node = node.next;
        }
    }

Answer 3

Here's two ways of doing this in java. the method used above works in O(n) but requires additional space. Where as the second version runs in O(n^2) but requires no additional space.

import java.util.Hashtable;

public class LinkedList {
LinkedListNode head;

public static void main(String args[]){
    LinkedList list = new LinkedList();
    list.addNode(1);
    list.addNode(1);
    list.addNode(1);
    list.addNode(2);
    list.addNode(3);
    list.addNode(2);

    list.print();
    list.deleteDupsNoStorage(list.head);
    System.out.println();
    list.print();
}

public void print(){
    LinkedListNode n = head;
    while(n!=null){
        System.out.print(n.data +" ");
        n = n.next;
    }
}

public void deleteDups(LinkedListNode n){
    Hashtable<Integer, Boolean> table = new Hashtable<Integer, Boolean>();
    LinkedListNode prev = null;

    while(n !=null){
        if(table.containsKey(new Integer(n.data))){
            prev.next = n.next;     //skip the previously stored references next node
        }else{
            table.put(new Integer(n.data) , true);
            prev = n;       //stores a reference to n
        }

        n = n.next;
    }
}

public void deleteDupsNoStorage(LinkedListNode n){
    LinkedListNode current = n;

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

}

public void addNode(int d){
    LinkedListNode n = new LinkedListNode(d);
    if(this.head==null){
        this.head = n;
    }else{
        n.next = head;
        head = n;
    }
}

private class LinkedListNode{
    LinkedListNode next;
    int data;

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

Answer 4

Try this it is working for delete the duplicate elements from your linkedList

package com.loknath.lab;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

public class Task {
    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);
        deleteDups(list);
        System.out.println(list);
    }

    public static void deleteDups(LinkedList<Integer> list) {
        Set s = new HashSet<Integer>();
        s.addAll(list);
        list.clear();
        list.addAll(s);

    }
}

Answer 5

I think you can just use one iterator current to finish this problem 

public void compress(){
    ListNode current = front;
    HashSet<Integer> set = new HashSet<Integer>();
    set.add(current.data);
    while(current.next != null){
       if(set.contains(current.next.data)){
          current.next = current.next.next;         }
         else{
            set.add(current.next.data);
            current = current.next;
         }
      }

}