從鏈表中刪除偶數但不在尾節點工作？

Question

void deleteEven() { 
     boolean con = false; 
     Node add; 
     Node move; 
     move = head; 
     if (move.data % 2 == 0) { 
      head = move.next; 
      con = true; 
     } 
     add = move; 
     move = move.next; 
     while (move != null) { 
      if (move.data % 2 == 0) { 
       add.next = move.next; 
       con = true; 
      } 
      add = move; 
      move = move.next; 
     } 
     if (!con) 
      System.out.println("No even numbers in list"); 
    } 

它適用於除尾部以外的每個節點。 如果鏈表是[5,4,3,2,2] 結果是[5,3,2] 如何解決這個問題？

Answer 1

的問題是不是與尾節點。問題在於連續的兩個節點，無論它們在列表中的什麼位置。當前節點即使您剛剛移除指針，也會將指針移動到前一個節點（add）當前節點。對於第二個偶節點，您的add.next = move.next語句將爲剛刪除的節點更改next。

最簡單的辦法是隻移動add如果節點是連：

if (move.data % 2 == 1) { 
    add.next = move.next; 
    con = true; 
} else { 
    add = move.next; 
} 

你可以相當多的通過簡化代碼擺脫add乾脆只是在尋找一個節點提前move：

while (move.next != null) { 
    if (move.next.data % 2 == 0) { 
     move.next = move.next.next; 
     con = true; 
    } else { 
     move = move.next; 
    } 
} 

併爲您提供一個編程技巧：在嘗試診斷問題之前有幾個測試用例。我發現基於少量測試用例很容易跳到一個不正確的結論，並且通常擴大範圍會使問題更加清晰。這是測試驅動開發和其確實起作用的（許多）原​​因之一。

Answer 2

讓我們創建服務節點來連接其他節點。

然後遍歷列表，並在一個新的列表複製引用（新節點不創建）：

void deleteEven() { 
    Node tmpHead = new Node(0, null); 
    Node tmpCopy = tmpHead; 
    Node tmp = head; 
    while (tmp != null) { 
     if (tmp.data % 2 == 1) { 
      tmpCopy.next = tmp; 
      tmpCopy = tmpCopy.next; 
     } 
     tmp = tmp.next; 
    } 
    tmpCopy.next = null; 
    head = tmpHead.next; 
} 

假設哪個節點是：

class Node { 
    int data; 
    Node next; 

    public Node(int data, Node next) { 
     this.data = data; 
     this.next = next; 
    } 
}