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

问题描述

  import java.util。*; 
 / * 
 *从未排序的链表中删除重复项
 * / 
 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; 
 //第n个节点不为null 
 while（head！= null）{
 //有重复的
 if（table.containsKey（head.data））{
 // skip duplicate 
 previous.next = head.next; 
} else {
 //将元素放入哈希表
 table.put（head.data，true）; 
 //移动到下一个元素
 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]

它不会消除重复。

解决方案

通过链接迭代列表，
将每个元素添加到哈希表。当我们发现一个重复的元素时，我们删除元素并继续迭代。我们可以一次通过，因为我们使用链表。

以下解决方案需要O（n）个时间，n是链接列表中的元素数。

  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）; 
上一个= n; 
} 
 n = n.next; 
} 
} 
  

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?

解决方案

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.

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屋！