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

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。如果我传入0，那么可能是删除head入口点，也就是删除整个列表？

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

Answer 1

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

head = null;

如果要删除的项目是头部，但您应该做的是，

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

    head = null;
}

这会将头部指向头部 + 1 个项目，除非头部是列表中的唯一项目。在那种情况下，我们应该将 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 2

你的问题就在这里

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

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

一个解决方法是

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

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

Answer 3

1) 删除(0)。 delete 永远不会进入循环，因为 i 小于 k 立即为真。所以你删除 head.item。 2) 然后删除特殊情况 2 集 head = null。

这是 2 个错误。没有冒犯，但您的代码一团糟。坐下来看图表，再次尝试从头开始解谜。别人为你做这件事只会教你如何尽早放弃编程问题。

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

  }

这给了我想要的输出。

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

How to delete the first element in a linked list?

java

linked-list