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

Ans is in C . first sorted link list sort() in nlog time and then deleted duplicate del_dip() .

node * partition(node *start)
{
    node *l1=start;
    node *temp1=NULL;
    node *temp2=NULL;
    if(start->next==NULL)
        return start;

    node * l2=f_b_split(start);
      if(l1->next!=NULL)
        temp1=partition(l1);
      if(l2->next!=NULL)
            temp2=partition(l2);

if(temp1==NULL || temp2==NULL)
    {
        if(temp1==NULL && temp2==NULL)
        temp1=s_m(l1,l2);

        else if(temp1==NULL)
        temp1=s_m(l1,temp2);

        else if(temp2==NULL)
        temp1=s_m(temp1,l2);
}
    else
            temp1=s_m(temp1,temp2);

    return temp1;
}

node * sort(node * start)
{
    node * temp=partition(start);
        return temp;
}

void del_dup(node * start)
{
  node * temp;
    start=sort(start);
    while(start!=NULL)
        {
        if(start->next!=NULL && start->data==start->next->data  )
            {
                temp=start->next;
                start->next=start->next->next;
                free(temp);
            continue;
            }
        start=start->next;
        }
}

void main()
 {
    del_dup(list1);
    print(list1);
} 

Answer 2

1.Fully Dynamic Approach 2.Remove Duplicates from LinkedList 3.LinkedList Dynamic Object based creation Thank you

import java.util.Scanner;
class Node{
    int data;
    Node next;
    public Node(int data)
    {
        this.data=data;
        this.next=null;
    }
}
class Solution
{
    public static Node insert(Node head,int data)
    {
    Node p=new Node(data);
    if(head==null)
    {
        head=p;
    }
    else if(head.next==null)
    {
        head.next=p;
    }
    else
    {
        Node start=head;
        while(start.next!=null)
        {
            start=start.next;   
        }
        start.next=p;
        return head;
        //System.out.println();
    }
    return head;    
    }
    public static void display(Node head)
    {
        Node start=head;
        while(start!=null)
        {
            System.out.print(start.data+" ");
            start=start.next;
        }

    }
    public static Node remove_duplicates(Node head)
    {
       if(head==null||head.next==null)
       {
           return head;
       }
       Node prev=head;
       Node p=head.next;

       while(p!=null)
       {
           if(p.data==prev.data)
           {
            prev.next=p.next;
            p=p.next;              
           }
           else{
               prev=p;
               p=p.next;   
           }
       }
       return head;
    }
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        Node head=null;
        int T=sc.nextInt();
        while(T-->0)
        {
            int ele=sc.nextInt();
            head=insert(head,ele);
        }
        head=remove_duplicates(head);
        display(head);  
    }
}

input: 5 1 1 2 3 3 output: 1 2 3

Answer 3

Try This.Its working. // Removing Duplicates in Linked List

import java.io.*;
import java.util.*;
import java.text.*;
class LinkedListNode{
    int data;
    LinkedListNode next=null;

    public LinkedListNode(int d){
        data=d;
    }
    void appendToTail(int d){
        LinkedListNode newnode = new LinkedListNode(d);
        LinkedListNode n=this;
        while(n.next!=null){
            n=n.next;
        }
        n.next=newnode;
    }

    void print(){
        LinkedListNode n=this;
        System.out.print("Linked List: ");
        while(n.next!=null){
            System.out.print(n.data+" -> ");
            n=n.next;
        }
        System.out.println(n.data);
    }
}
class LinkedList2_0
{
    public static void deletenode2(LinkedListNode head,int d){
        LinkedListNode n=head;
        // If It's head node
        if(n.data==d){
            head=n.next;
        }
        //If its other
        while(n.next!=null){
            if(n.next.data==d){
                n.next=n.next.next;
            }
            n=n.next;
        }
    }

    public static void removeDuplicateWithBuffer(LinkedListNode head){
        LinkedListNode n=head;
        LinkedListNode prev=null;
        Hashtable<Integer, Boolean> table = new Hashtable<Integer, Boolean>();
        while(n!=null){
            if(table.containsKey(n.data)){
                prev.next=n.next;
            }
            else{
                table.put(n.data,true);
                prev=n;
            }
            n=n.next;
        }
    }
    public static void removeDuplicateWithoutBuffer(LinkedListNode head){
        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;
        }
    }
    public static void main(String[] args) throws java.lang.Exception {
        LinkedListNode head=new LinkedListNode(1);
        head.appendToTail(1);
        head.appendToTail(3);
        head.appendToTail(2);
        head.appendToTail(3);
        head.appendToTail(4);
        head.appendToTail(5);
        head.print();

        System.out.print("After Delete: ");
        deletenode2(head,4);
        head.print();

        //System.out.print("After Removing Duplicates(with buffer): ");
        //removeDuplicateWithBuffer(head);
        //head.print();

        System.out.print("After Removing Duplicates(Without buffer): ");
        removeDuplicateWithoutBuffer(head);
        head.print();

    }
}

Answer 4

LinkedList<Node> list = new LinkedList<Node>();

 for(int i=0; i<list.size(); i++){
        for(int j=0; j<list.size(); j++){
            if(list.get(i).data == list.get(j).data && i!=j){
                if(i<j){
                     list.remove(j);
                    if(list.get(j)!= null){
                         list.get(j-1).next = list.get(j);
                    }else{
                        list.get(j-1).next = null;
                    }

                }
                else{
                    if(i>j){
                        list.remove(i);
                        if(list.get(i) != null){
                            list.get(j).next = list.get(i);
                        }else{
                            list.get(j).next = null;
                        }

                    }
                }

            }

        }
    }

Answer 5

You can use the following java method to remove duplicates:

1) With complexity of O(n^2)

public void removeDuplicate(Node head) {
    Node temp = head;
    Node duplicate = null;                //will point to duplicate node
    Node prev = null;                     //prev node to duplicate node
    while (temp != null) {                //iterate through all nodes       
        Node curr = temp;
        while (curr != null) {                     //compare each one by one
            /*in case of duplicate skip the node by using prev node*/
            if (curr.getData() == temp.getData() && temp != curr) {        
                duplicate = curr;
                prev.setNext(duplicate.getNext());
            }
            prev = curr;
            curr = curr.getNext();
        }
        temp = temp.getNext();
    }
}

Input:1=>2=>3=>5=>5=>1=>3=>

Output:1=>2=>3=>5=>

2)With complexity of O(n) using hash table.

public void removeDuplicateUsingMap(Node head) {
    Node temp = head;
    Map<Integer, Boolean> hash_map = new HashMap<Integer, Boolean>(); //create a hash map
    while (temp != null) {  
        if (hash_map.get(temp.getData()) == null) {  //if key is not set then set is false
            hash_map.put(temp.getData(), false);
        } else {                                   //if key is already there,then delete the node
            deleteNode(temp,head);
        }
        temp = temp.getNext();
    }

}

public void deleteNode(Node n, Node start) {
        Node temp = start;
        if (n == start) {
            start = null;
        } else {
            while (temp.getNext() != n) {
                temp = temp.getNext();
            }

            temp.setNext(n.getNext());

        }
    }

Input:1=>2=>3=>5=>5=>1=>3=>

Output:1=>2=>3=>5=>

Answer 6

here are a couple other solutions (slightly different from Cracking coding inerview, easier to read IMO).

public void deleteDupes(Node head) {

Node current = head;
while (current != null) {
    Node next = current.next;
    while (next != null) {
        if (current.data == next.data) {
            current.next = next.next;
            break;
        }

        next = next.next;
    }

    current = current.next;
}

}

public void deleteDupes(Node head) {
Node current = head;
while (current != null) {
    Node next = current.next;
    while (next != null) {
        if (current.data == next.data) {
            current.next = next.next;
            current = current.next;
            next = current.next;
        } else {
            next = next.next;
        }
    }

    current = current.next;
}

}