在Java中从链表中删除重复项而不使用额外的缓冲区

Question

我正在审查即将进行的测试的一些代码片段.我在笔记中看到了这一点,刚才意识到方法1的代码实际上并没有删除重复项,如果列表是这样的A - > B - > C - > A.我写了一个替代函数(方法2)我认为实际上会有效.你们有什么感想？方法1实际上不起作用,我在追踪错误吗？ps我们目前不允许编译器:)

这是代码,简要介绍它应该做什么.

方法1:当头部和尾部有两个确切的东西时,我认为不起作用.编写代码以从没有缓冲区的未排序列表中删除重复项.Wwe可以用两个指针迭代:"current"执行正常迭代,而"runner"遍历所有先前节点以检查重复.Runner每个节点只能看到一个重复,因为如果有多个重复项,它们就已经被删除了.

public static void deleteDuplicates1(LinkedListNode head) {
if (head == null) return;
LinkedListNode previous = head;
LinkedListNode current = previous.next;
while (current != null) {
    LinkedListNode runner = head;
       while (runner != current) { // Check for earlier dups
          if (runner.data == current.data) {
              LinkedListNode tmp = current.next; // remove current
              previous.next = tmp;
              current = tmp; // update current to next node
              break; // all other dups have already been removed
              }
              runner = runner.next;
          }
          if (runner == current) { // current not updated - update now
               previous = current;
               current = current.next;
              }
         }
 }

我以为这会起作用.方法2:

    public void removeDuplicates2(){  
    Node current = null;  
    Node tracer = null;  

   for( current = head.next; current!=null; current=current.next){  
       for(tracer=head; tracer!=current; tracer=tracer.next){  
          if(tracer.data == current.data)  
          //DELETE THE NODE IN CURRENT  
       }  
    }  

}

Answer 1

最好的方法是对链表进行排序.然后迭代并检查相邻元素是否相同.如果是,请删除相邻元素.这是一种不使用额外缓冲区的O(nlogn)方法.

Answer 2

我不确定"没有额外的缓冲区"对你意味着什么,但由于我是一个懒惰的人,因为我认为其他人在编写算法方面比我好得多,所以我将整个链表放入HashSet并返回链表.这将轻松删除重复:

LinkedList result = new LinkedList(new HashSet(inputList));

或者,如果要保留元素的顺序

LinkedList result = new LinkedList(new LinkedHashSet(inputList));

既然这是一个家庭作业问题,你似乎自己实现了一个LinkedList,很可能这个解决方案不可行;-)但无论如何,它将具有O(n)复杂性,而不是O(n) ^ 2)喜欢你的方法1和2,这对你来说可能已经好多了......？