删除传统链表中的重复项

Question

我知道有更好的方法可以用hashSets做到这一点。等等，但我想用旧的方式做这件事。这是我为消除重复项而编写的函数，一个棘手的情况是，如果重复项是最后一个节点，我必须为它编写一个特殊情况。我这样做是否正确，我觉得这太笨拙了。

// Assume list like this: 0->1->2->3->4->0
//and want to remove 0 in this example
  //O(n^2)
public void removeDuplicatesV1(){
  Node current, itr;
  itr = head;
  if(head !=null){
      while(itr!=null && itr.getNext()!=null){  //ptr1
          current = itr;
          while(current.getNext()!=null){   //ptr2
              if(itr.getItem().equals(current.getNext().getItem())){
                  if(current.getNext().getNext()== null){ //look ahead if last node is a dup
                      current.setNext(null);              
                      break;
                  }
                  else
                      current.setNext(current.getNext().getNext());
              }
              current = current.getNext();
          }
          itr = itr.getNext();
      }
  }

}

Answer 1

从第一个 while 循环中删除 itr.getNext（）！=null。

// Assume list like this: 0->1->2->3->4->0
//Code below won't remove the last 0
//O(n^2)
public void removeDuplicatesV1(){
  Node current, itr;
  itr = head;
  if(head !=null){
      while(itr!=null ){  //slow ptr for outer loop, will be checked against fast pointer
          current = itr;
          while(current != null && current.getNext()!=null){ //inner loop, current ptr moves  down the list
              if(itr.getItem() == current.getNext().getItem())
                  current.setNext(current.getNext().getNext());
              current = current.getNext();
          }
          itr = itr.getNext();
      }
  }