如何删除链接列表中的特定节点

Question

我以前需要帮助调试我的deleteNode方法。它现在可以工作（下面更新版本），但我希望它能够提供必须删除头节点的情况。目前，它返回NullPointerException，我在deleteNode中插入了*。我不知道当时我的任何变量都可以为null，看到我的while循环要求position和head首先不为null。

public class LinkedList 
{ 
private class Node 
{ 
    int item; 
    Node link; 

    @SuppressWarnings("unused") 
    public Node() 
    { 
     item = Integer.MIN_VALUE; 
     link = null; 
    } 
    public Node(int x, Node p) 
    { 
     item = x; 
     link = p; 
    } 
} 

private Node head; 

public LinkedList() 
{ 
    head = null; 
} 

public boolean deleteNode (int target) 
{ 
    Node position = head; 
    boolean isGone = false; 

    while(position != null && head != null) 
    { 
     if(position.link == head && position.link.item == target) 
     { 
      head = head.link; 
      isGone = true; 
      return isGone; 
     } 
    *** else if(position.link.item == target && position.link != head) 
     { 
      position.link = position.link.link; 
      isGone = true; 
      return isGone; 
     } 
     position = position.link; 
    } 
    return isGone; 
} 

public void printList() 
{ 
    System.out.println("Your list is: "); 
    Node position = head; 
    while(position != null) 
    { 
     System.out.println(position.item + " "); 
     position = position.link; 
    } 
    System.out.println(); 
} 
} 

Answer 1

LinkedList.deleteNode(int)从来没有改变任何节点的link，所以它不会从列表中删除任何元素。

假设nodeA.link == nodeB和nodeB.item == target。然后你需要设置nodeA.link = nodeB.link，这样就没有任何东西指向nodeB了。

Answer 2

看看你的deleteNode（）while循环代码。

while(position != null && counter != null) 
    { 
     itemAtPosition = position.item; 
     if(itemAtPosition == target) 
     { 
      position = position.link; 
      isGone = true; 
     } 
     counter = counter.link; 
    } 

您更新计数器，但从未参考它。位置永不改变，所以

if(itemAtPosition == target) 

行从不返回true。我怀疑你需要检查counter.item的地方！

Answer 3

首先，您并未针对目标项目位于开头的情况编写代码，其中头部应该相应地更新。其次，比较项目在遍历列表期间从不更新。

Answer 4

这里是我看到的问题的列表：

1. 你真的想使用，position普查员，从不更新。不需要更新的枚举器，counter。

2. 你永远不会真的删除节点。为了移除节点，您需要将前一个节点的链接设置为匹配节点的链接，从而将其从链中移除。

3. 你没有处理特殊情况。如果传递的列表为空，会发生什么？如果匹配节点是第一个节点会发生什么？最后一个节点？

4. 您应该从调用函数返回链表的头部。这是删除链接列表的头节点时所必需的。

由于这是一个家庭作业问题，请尽量为自己解决问题，但希望这些问题对您有帮助。