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

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

方法1:当头部和尾部有2个确切的东西时,我认为这是行不通的。
编写代码以从没有排序的列表中删除重复项而无需缓冲区。 Wwe可以使用两个指针进行迭代:“ current”进行常规迭代,而“ runner”对所有先前的节点进行迭代以检查是否存在重复。 Runner在每个节点上只会看到一个dup,因为如果有多个重复项,它们将已经被删除。

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

}

最佳答案

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

关于java - 在Java中从链接列表中删除重复项,而无需使用额外的缓冲区,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/4578928/

10-11 22:59
查看更多