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

結果: [1, 2, 3, 3, 3, 4, 4] [1, 2, 3, 3, 3, 4, 4]

重複は排除されません。

メソッドが機能しないのはなぜですか？

4

19 に答える 19

6
  1. あなたが提供した解決策は、元のリストを変更しません。
  2. 元のリストを変更して重複を削除するには、2 つのポインターを使用して反復できます。Current: LinkedList を反復処理し、以降のすべてのノードの重複をチェックする runner 。

  3. 以下のコードは O(1) 空間で実行されますが、O(N 平方) 時間です。

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

    }

参照 : ゲイル・ラークマン・マクダウェル

于 2013-08-24T17:43:07.237 に答える
3

Java でこれを行うには、次の 2 つの方法があります。上記の方法は O(n) で機能しますが、追加のスペースが必要です。2 番目のバージョンは O(n^2) で実行されますが、追加のスペースは必要ありません。

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;
    }
}
}
于 2014-04-11T18:43:32.883 に答える
2

次の Java メソッドを使用して、重複を削除できます。

1) O (n^2)complexityの場合

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

入力:1=>2=>3=>5=>5=>1=>3=>

出力:1=>2=>3=>5=>

2 )ハッシュ テーブルを使用したO(n)complexityの場合。

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

        }
    }

入力:1=>2=>3=>5=>5=>1=>3=>

出力:1=>2=>3=>5=>

于 2016-01-03T00:22:34.093 に答える
1

これを試してください。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);

    }
}
于 2014-04-21T06:23:35.653 に答える
0

これを試してみてください。// リンクされたリストの重複を削除

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

    }
}
于 2014-08-09T06:42:37.450 に答える
0 
/**
*
* 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;
    }
}
于 2015-05-05T19:17:42.167 に答える
0

一番の問題は、

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

headの内容で実際に初期化するわけではありませんlist。list.getFirst()単純に Integer1を返し、その唯一の要素としてhead含まれています。すべての要素を取得するには、ループし1て初期化する必要があります。headlist

さらに、

Task.deleteDups(head)

を変更するheadと、これは完全に変更されないままになります。 への変更が に伝播するlist理由はありません。したがって、メソッドを確認するには、再度出力するのではなく、ループ ダウンして各要素を出力する必要があります。headlistheadlist

于 2013-07-27T21:03:41.977 に答える
0

これは私のJavaバージョンです

//  Remove duplicate from a sorted linked list
public void removeDuplicates() {

        Node current = head;
        Node next = null;
        /* Traverse list till the last node */
        while (current != null) {
            next = current;

            /*
             * Compare current node with the next node and keep on deleting them until it
             * matches the current node data
             */
            while (next != null && current.getValue() == next.getValue()) {

                next = next.getNext();

            }

            /*
             * Set current node next to the next different element denoted by temp
             */
            current.setNext(next);
            current = current.getNext();
        }
    }
于 2020-11-19T03:01:16.690 に答える