如何刪除鏈接列表中的特定節點

我以前需要幫助調試我的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

如何刪除鏈接列表中的特定節點

回答

相關問題