从未排序的链表中删除重复项 [英] Remove duplicates from an unsorted linked list

问题描述

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]

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

它不会消除重复.

为什么方法不起作用?

推荐答案

遍历链表，将每个元素添加到哈希表中.当我们发现重复元素时，我们删除该元素并继续迭代.由于我们使用的是链表，因此我们可以一次性完成所有操作.

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.

下面的解需要O(n)时间，n是链表中元素的个数.

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

这篇关于从未排序的链表中删除重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！