从未排序的链接列表中删除重复项

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

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

它不会消除重复.

为什么这个方法不起作用？

Answer 1

迭代链表,将每个元素添加到哈希表中.当我们发现重复元素时,我们删除元素并继续迭代.我们可以在一次通过中完成所有操作,因为我们使用链表.

以下解决方案需要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);
          previous = n;
      }
      n = n.next;
  }
}

Answer 2

1. 您提供的解决方案不会修改原始列表.
2. 要修改原始列表并删除重复项,我们可以使用两个指针进行迭代.Current:迭代LinkedList,以及用于检查所有后续节点是否重复的运行器.

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

   }

参考:Gayle laakmann mcdowell