如何删除链表中的第一个元素

Question

我正试图编写一个函数delete()，它需要一个链表并从列表中删除第k个元素。我的代码如下:

public void delete(int k){
  Node current = head;
  for (int i = 0; i < k; i++){
      if(current == null || current.next == null){ //check if list is empty or k is out of bounds
          throw new IndexOutOfBoundsException();
          }
      else 
      {
          current = current.next; // Move pointer to k position
      }
  }
  remove(current.item);
  N--;  
  }
public void remove(E e) {
if (e == null)
  throw new NullPointerException();
// (*) special case (2/one node with e)
if (head != null && head.item.equals(e)) {
  head = null;
  N--;
}
else { // (*) general case (3) -- this also covers the case for empty list
  Node temp;
  // Step 1: bring temp to one node before the node with e.
  for (temp = head; temp != null && !temp.next.item.equals(e);
       temp = temp.next) {} // empty body
  // Step 2: if temp is still in the list, then remove
  if (temp != null) {
    temp.next = temp.next.next;
    --N;
  }
}

}

到目前为止，当我在main中运行lst1.delete(1)或lst1.delete(2)等命令时，我的代码工作正常。然而，当我运行lst1.delete(0)时，它删除了整个链表。我无法弄清楚为什么lst1.delete(0)删除整个链表，但我认为这与for循环有关。for循环循环到比k小1为止，如果我传入0，那么它可能会删除头入口点，也就是删除整个链表?

我的问题是，有没有人能告诉我如何改变我的代码，以便当我运行lst1.delete(0)时，它只是删除链表中的第一个元素，而不是整个链表?

Answer 1

1) delete(0)。Delete永远不会进入循环，因为I小于k是直接为真。移除head。item。2)然后去掉特例2集head = null。

有两个错误。无意冒犯，但你的代码真是一团糟。坐下来拿着图表，从头再试一次。别人帮你做这件事，除了教你如何尽早放弃编程问题之外，什么也教不了你。

Answer 2

你的问题在这里

if (head != null && head.item.equals(e)) {
     head = null;
     N--;
}

如果您使用lst1.delete(0)，那么当您将head传递给remove()时，head.item.equals(e)变为true。然后你的整个链接被删除。

一个修复方法是

 if (head != null && head.item.equals(e)&&head.next==null) {
     head = null;
     N--;
}

这里额外检查head.next==null确保链表中只有一个元素

Answer 3

这应该可以解决您的问题。您正在设置

head = null; 

如果要删除的项目是标题，但你应该做的是，

if(head.next() != null) {
    head = head.next();
}
else {
    head = null;
}

这将指向head + 1项，除非head是列表中唯一的项。在这种情况下，我们应该将head设置为null。

public void delete(int k) {
    Node current = head;
    for (int i = 0; i < k; i++){
        if(current == null || current.next == null) { //check if list is empty or k is out of bounds
            throw new IndexOutOfBoundsException();
        }
        else {
            current = current.next; // Move pointer to k position
        }
    }
    remove(current.item);
    N--;  
}
public void remove(E e) {
    if (e == null) {
        throw new NullPointerException();
    }
    // (*) special case (2/one node with e)
    if (head != null && head.item.equals(e)) {
        //Your issue was here
        if(head.next() != null) {
            head = head.next();
        }
        else {
            head = null;
        }
        N--;
    }
    else { // (*) general case (3) -- this also covers the case for empty list
        Node temp;
        // Step 1: bring temp to one node before the node with e.
        for (temp = head; temp != null && !temp.next.item.equals(e);
            temp = temp.next) {} // empty body
            // Step 2: if temp is still in the list, then remove
            if (temp != null) {
                temp.next = temp.next.next;
                    --N;
            }
        }
    }
}

Answer 4

这是因为当k = 0时，永远不会进入循环。因此，current没有更新为指向正确的。

Answer 5

我想出了另一个甚至不调用remove方法的方法。因为我不是最初编写remove方法的人，所以我更喜欢下面的代码，因为只要方法调用，它就会保持在自己的内部。

public void delete(int k){
  //instance variable
  Node current = head;
  if(current == null || current.next == null){ //check if list is empty
      throw new NullPointerException();
      }
  if (k < 0 || k >= size()){                  // check if k is out of bounds
      throw new IndexOutOfBoundsException();
      }
  if (k == 0){                                // this handles k = 0 condition
      head = head.next;
  }
  else
  for (int i = 0; i < k-1; i++){              // otherwise, if K != 0,
      current = current.next;                 // move pointer to k position
  }
  if (current != null) {
        current.next = current.next.next;
  }
  N--;  
  }

这给了我我所希望的输出