Entfernen Sie Duplikate aus einer unsortierten verketteten Liste

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

Das Ergebnis: [1, 2, 3, 3, 3, 4, 4]
[1, 2, 3, 3, 3, 4, 4]

Beseitigt Sie nicht die Duplikate.

Warum nicht die Methode funktioniert?

stackoverflow.com/questions/9459557/...
Sie sind überhaupt nicht der Rückkehr die neue Liste von der deleteDups Methode.
Ich schlage vor, Sie verwenden Sie Ihre debugger in der IDE Schritt für Schritt durch den code und verstehen. Wenn Sie nicht wissen, wie es zu benutzen, es ist nie zu spät zu lernen. Würde ich auch nicht verwenden, Hashtable, wie es ist ein Erbe der Klasse für die letzten 15 Jahre oder so. Sie sollten die Verwendung von einem Satz wie HashSet.
Ihre Liste ist nicht angeschlossen. Sie sind nur das hinzufügen von Knoten, sondern Ihre Funktion zurück, sofort, weil jedes element nicht ein "weiter" - Zeiger gesetzt

InformationsquelleAutor Ivan | 2013-07-14

11

Durchlaufen die verkettete Liste
hinzufügen jedes element in eine Hashtabelle. Wenn wir entdecken, ein doppeltes element, entfernen wir das element und die das fortsetzen des Durchlaufs. Wir können dies tun, alle in einem Durchlauf-da sind wir mit einer verlinkten Liste.

Folgende Lösung in O(n) Zeit, n die Anzahl der Elemente in der verknüpften Liste.
```
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;
  }
}
```
Warum benutzen Sie HashMap statt HashSet? Der Wert des Schlüssel ist hier überflüssig. Obwohl HashSet wird unterstützt von HashMap, aber es macht keinen Sinn, die ist nicht erforderlich, durch das design.
hat jemand schon das Lesen cracking the coding interview
Die entsprechende Datenstruktur, die hier verwendet werden ist ein HashSet und nicht eine Karte, und sicherlich keine Karte, die thread-sicher sind.
Was ist vorige verwendet für hier? Warum wird sowas wie unten nicht funktionieren? ~~~ public static void deleteDups (LinkedListNode n){ HashSet<Integer> set = new HashSet<Integer>(); while(n!=null){ if(set.containsKey(n.Daten)){ n=n.weiter } else { Tabelle.put(n)).Daten, true); n=n.next; } } } ~~~

InformationsquelleAutor user3000711
5
1. Die Lösung, die Sie gestellt haben, nicht ändern Sie die ursprüngliche Liste.
2. So ändern Sie die ursprüngliche Liste und entfernen Sie Duplikate, können wir die Iteration mit zwei Zeigern. Strom: die durchläuft LinkedList, und Läufer, die prüft, ob alle nachfolgenden Knoten für Duplikate.
3. Den code unten läuft in O(1) Speicherplatz, aber O(N Quadrat) Zeit.
  
  public void deleteDups(LinkedListNode Kopf){
```
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;
}
```
  }
Referenz : Gayle laakmann mcdowell

Maxime : Sorgfalt, um upvote, wenn Sie denken, dass die Lösung richtig ist ? 🙂
Es ist nicht die optimale Lösung, das ist, warum ist nicht die richtige Antwort.
Ich habe nie argumentiert, dass meine Lösung optimal ist (bereits erläutert in der Lösung). Nur weil die Lösung nicht optimal ist, bedeutet nicht, dass die Lösung nicht korrekt ist.
Diese gleiche Lösung ist in Cracking the coding interview
Rambo7, ich denke deine Lösung wird nicht funktionieren, wenn der doppelte-ist das Letzte element der Liste, wo die Läufer.next!=null-check schlägt fehl. Habe ich nicht getestet, aber probieren Sie etwas wie dieses: //0 1 2 3 4 1

InformationsquelleAutor Rambo7

Hier sind zwei Möglichkeiten, dies zu tun, in java. die Methode oben funktioniert in O(n) erfordert jedoch zusätzlichen Speicherplatz. Wo da die zweite version läuft in O(n^2), aber benötigt keinen zusätzlichen Platz.

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

InformationsquelleAutor Peter

Ans in C . zuerst sortierte link-Liste mit sort() in nlog Zeit und dann gelöscht, doppelte 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);
}

InformationsquelleAutor Aditya_G

Versuchen Sie dies, es ist die Arbeit für löschen der doppelten Elemente aus der 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);

    }
}

ich denke die user die hier erwartet wird, schreiben Sie Ihre eigene Implementierung von linkedlist und dann Duplikate entfernen und nicht einfach die LinkedList-Klasse in der JAVA-API-Duplikate entfernen
Abgesehen von der Verwendung der JAVA-API hinzufügen, die Liste zu setzen, wird die Sortierung der Elemente. Dies steht im Widerspruch zu der Problematik, der Umgang mit der UNSORTIERTEN Liste.

InformationsquelleAutor loknath

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

}

InformationsquelleAutor Big_t boy

Können Sie die folgende java-Methode remove duplicates:

1) Mit complexity von 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();
    }
}

Eingang:1=>2=>3=>5=>5=>1=>3=>

Ausgabe:1=>2=>3=>5=>

2)Mit complexity von O(n) mit hash-Tabelle.

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());

        }
    }

Eingang:1=>2=>3=>5=>5=>1=>3=>

Ausgabe:1=>2=>3=>5=>

InformationsquelleAutor Prateek Joshi

0

Das erste problem ist, dass
```
LinkedListNode head=new LinkedListNode(list.getFirst());
```
eigentlich nicht initialisieren head mit dem Inhalt list. list.getFirst() gibt einfach die Integer -1, und head enthält 1 als einziges element. Sie hätte zu initialisieren head durch Durchlaufen list um alle Elemente.

Darüber hinaus, obwohl
```
Task.deleteDups(head)
```
ändert head werden, lässt dies list völlig unverändert—es gibt keinen Grund, warum die änderungen head verbreiten sollten, um list. Daher, um zu überprüfen, Ihre Methode, Sie müssten die Schleife unten head und drucken Sie jedes element, eher als Ausdruck list wieder.

InformationsquelleAutor ikdc

Versuchen.Ihre arbeiten.
//Entfernt Duplikate in der Verlinkten Liste

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();

    }
}

InformationsquelleAutor Veer

hier sind ein paar andere Lösungen, die geringfügig von Rissbildung Kodierung inerview, leichter zu Lesen, 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;
}

}

InformationsquelleAutor alexD

Hier ist eine sehr einfache 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);

Sehr prägnant. Ist es nicht?

InformationsquelleAutor Alex

Es ist einfach Weg, ohne HashSet oder die Schaffung von Knoten.

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

Und, um es zu überprüfen:

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

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

InformationsquelleAutor Den

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

                    }
                }

            }

        }
    }

InformationsquelleAutor Joe Sleiman

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

InformationsquelleAutor Gaya3

Folgenden code implementiert dies, ohne dass Sie alle temporären Puffer. Es beginnt mit dem Vergleich der ersten und zweiten Knoten, wenn nicht ein Spiel, es fügt char auf den ersten Knoten zum zweiten Knoten geht dann vergleicht man alle chars in der zweiten Knoten zu char am Dritten Knoten und so weiter. Nach comperison abgeschlossen ist, vor dem verlassen des Knotens, auf dem er löscht alles, was Hinzugefügt wird, und stellt die alten Werte, welche sich auf Knoten.val.char(0)

F > FO > FOL > (Spiel gefunden, Knoten.next = Knoten.weiter.next) > (wieder übereinstimmen, ersetzen Sie es) > 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;
        }
    }

InformationsquelleAutor Berk

Alle Lösungen gegeben oben sieht optimiert, aber die meisten von Ihnen definiert benutzerdefinierte Knoten als Teil der Lösung. Hier ist eine einfache und praktische Lösung, die mit Java LinkedList und HashSet, die nicht darauf beschränken, verwenden Sie die bereits vorhandenen Bibliotheken und Methoden.

Zeit-Komplexität : O(n)

Speicherplatz-Komplexität: 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;
}

Diese behält auch der Reihenfolge der Liste.

InformationsquelleAutor Monil Panchal

-1

1.Voll Dynamische Ansatz
2.Entfernen Sie Duplikate von LinkedList
3.LinkedList Dynamische Objekt-basierte Entwicklung
Danke

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

Eingang:
5
1 1 2 3 3
Ausgabe:
1 2 3

InformationsquelleAutor Asif Bilakhiya

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.