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

我以前需要帮助调试我的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(); 
} 
}

来源

2011-11-29 murkyo0ocrimson

使用调试器，并找出它没有正确做什么 –

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

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

来源

2011-11-29 03:03:52 ruakh

看看你的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的地方！

来源

2011-11-29 03:04:11 user949300

我同意，位置和计数器，你只需要使用一个。这里的想法是只使用一个节点作为当前节点，并保持指定current_node = current_node.link直到找到目标。 – longbkit

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

来源

2011-11-29 03:12:31 kevinhyunilkim

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

你真的想使用，position普查员，从不更新。不需要更新的枚举器，counter。
你永远不会真的删除节点。为了移除节点，您需要将前一个节点的链接设置为匹配节点的链接，从而将其从链中移除。
你没有处理特殊情况。如果传递的列表为空，会发生什么？如果匹配节点是第一个节点会发生什么？最后一个节点？
您应该从调用函数返回链表的头部。这是删除链接列表的头节点时所必需的。

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

来源

2011-11-29 03:31:21 link664

谢谢你的观点，但是你能解释第二点吗？如果我理解正确，我的代码'position = position.link'继续到下一个链接，基本遍历列表，但实际上没有做任何事情。我想我不知道如何删除链接而不使用'position'和'counter'。 – murkyo0ocrimson

这是正确的。如果这是一个单链表，那么你应该做的是实际上与current.next比较，在这种情况下，它是'position.link.item'，那么如果这是匹配，则删除'position.link '，即'position.link = position.link.link'。只要确保你在这个'while'循环之前解释了头节点是要删除的节点的特殊情况。 – link664

非常感谢！我发现了这个bug，现在这个循环很完美。 – murkyo0ocrimson

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

回答

相关问题