从链表中删除节点

Question

我试图从链表中删除给定的节点。我不知道为什么我的代码不工作。有提示吗?我有[11,21,31,41]题目要求我删除索引为2的节点在这种情况下是31。到目前为止，我有这个:

public void delete (int k) {
    //[ 11 21 31 41 ].delete( 2 ): expected=[ 11 21 41 ]
    if (k < 0 || k >= N) throw new IllegalArgumentException ();
    for(Node x = first; x != null; x = x.next) {
        //deletes node
        if(x.item == k){
            x = x.next;
        }
        if(x.item <= k){
            x = x.next.next;
        }
    }

}

谁能告诉我为什么这个不工作?谢谢你

Answer 1

您可以使用next k次移动节点。存储临时整型和前一个节点。每次调用next()时减少临时int。一旦你在0(所需的元素)，通过设置前一个节点的下一个指针到x的下一个指针来删除，然后将x设置为null。

我认为在你的代码中，你错过了指针设置的部分。

例如:

(1) -> (2) -> (3)

删除(2)，设置(1).next = (3)和(2) = null。这将得到:

(1) -> (3)

Answer 2

这里有几个地方出了问题，我鼓励您进行一些println调试，以便在开发过程中更好地理解问题。

1. 假设item字段是节点的值，您将该节点的值与该节点的索引(例如x.item == k)进行比较。

2. 你要遵循的一般逻辑是，"如果迭代器指向的节点是我列表中的下一个节点，则将我的next设置为它的next。"

Answer 3

在您的代码中，您正在比较node的值与您传递的索引。这个比较总是索引小于节点中的值。在此之后，当您假设代码是正确的时，您也不会更新节点。

下面的代码应该会给出结果。

public void delete (int k)
{
//[ 11 21 31 41 ].delete( 2 ): expected=[ 11 21 41 ]
if (k < 0 || k >= N) throw new IllegalArgumentException ();
int count = 0;//Assuming index starts from 0
Node prev;
for(Node x = first; x != null; x = x.next)
{
    //deletes node
    count++;
    if(count<k)
    {
        prev = x;
        continue;
    }
    else
    {
        prev.next = x.next;
        x.next = null;
        break;
    }
}
if(count>k || count<k)
{
    System.out.println("No element with index k");
}
}

Answer 4

@花瓶是正确的说法

假设item字段是Node的值，则进行比较节点的值对应于该节点的索引(例如x.p item == k)。

一些可以修复这个问题的示例代码

public void delete(int k){
   Node n = first;
   for(int i = 0; i < k-1; i++){ // this loop finds the node right before the 
   n=n.next;                    // index to use to delete the desired index.
}
   n.next = n.next.next; // delete command
}