java - 在不使用额外缓冲区的情况下从 Java 中的链表中删除重复项

Question

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

这是代码，以及它应该做什么的简短介绍。

方法 1:当头部和尾部有 2 个确切的东西时，我认为不起作用。 编写代码以在没有缓冲区的情况下从未排序的列表中删除重复项。 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;
              }
         }
 }

我以为这会奏效。 方法二:

    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) 方法。