迭代法：仅使用一个引用变量删除链表节点

Question

已解决：代码反映了解决方案

我一直在处理自定义链表，需要仅使用 对列表的引用.

来删除具有给定键的节点

我已经设法用两个引用（上一个节点，当前节点）做到了这一点，但我对如何只使用一个引用有点困惑。

我的代码适用于尝试删除“88”或不存在的节点“100”时删除头节点和不在列表中的节点（我得到空指针异常）的情况。

Here is my test data from the list:
0) 88
1) 2
2) 1
3) 8
4) 11

// Iterative method to delete a node with a given integer key
// Only uses ONE reference variable to traverse the list.
private void delete (int key, Node x) {

    // Check if list is empty
    if (isEmpty()) {
        System.out.println("Cannot delete; the list is empty.");
    }

    // Check if we're deleting the root node
    if (key == head.getKey()) {

        // Now the first in the list is where head was pointing
        removeFromHead();
    }

    // General case: while the next node exists, check its key
    for (x = head; x.getNext() != null; x = x.getNext()) {

        // If the next key is what we are looking for, we need to remove it
        if (key == x.getNext().getKey()) {

            // x skips over the node to be deleted.
            x.putNext(x.getNext().getNext());
        }
    } // End for
}

Answer 1

好吧，您对列表的头部和尾部有问题，因为您没有正确检查它们。在进入 while 循环之前，您应该比较 key 和 head 。循环检查的第一个值是第二个节点 (temp.getNext().getKey())，因此您永远不会真正测试头部。此外，在循环结束并且您检查键是否在最后一个节点中之后，您还调用了 getNext()。如果它确实是最后一个节点，那么下一个节点为 null 并且它没有 getKey() 方法。

Answer 2

试试这个：

public Value delete (int key) {

    //check if list is empty
    if (head == null)
        //the key does not exist. return null to let the method caller know
        return null; 

    //check if we're deleting the root node
    if (key == head.getKey()) {
        //set the value of what we're deleting
        Value val = head.getNode().getValue();
        //now the first in the list is where head was pointing
        head = head.getNext();
        //there is now one less item in your list. update the size
        total--;
        //return what we're deleting
        return val;
    }

    // general case: while the next node exists, check its key
    for (Node x = head; x.getNext() != null; x = x.getNext()) {

        //check if the next node's key matches
        if (key == x.getNext().getKey()) {

            //set value of what we're deleting
            Value val = x.getNext().getNode().getValue();

            //x now points to where the node we are deleting points
            x.setNext(x.getNext().getNext());

            //there is now one less item in the list. update the size
            total--;

            //return what we're deleting
            return val; 
        }
    }


    //if we didn't find the key above, it doesn't exist. return null to let the
    // method caller know.
    return null; 
}

这是针对 LinkedList<code><Value> 的。总体思路就在那里，但您必须根据您的设置方式对其进行调整。

迭代法：仅使用一个引用变量删除链表节点

Iterative method: Delete Linked List node using only one reference variable

java

iteration

linked-list