爲什麼我不能刪除鏈接列表中的事件？

Question

問題：給定一個值，從鏈表中刪除該值的所有實例。 下面更多信息： JAVA

/** 
* Definition for singly-linked list. 
* public class ListNode { 
*  int val; 
*  ListNode next; 
*  ListNode(int x) { val = x; } 
* } 
*/ 
public class Solution { 
    public ListNode removeElements(ListNode head, int val) { 
     ListNode n = head; //1, 2, 6, 3, 4, 5, 6 
     while(n.next == null){ 
      if(n.next.val == val){ 
       n.next = n.next.next; 
      } 
      n = n.next; 
      if(n == null){break;} 
     } 
     return head; 
    } 
} 

自通的參考，應更新不應該嗎？

我想：

removeElements([1,2,6,3,4,5,6], 6) 

但它並沒有刪除任何東西。那麼我做錯了什麼？

Answer 1

有幾個問題：

• 要循環，直到一個節點爲null直到不爲空（即while(... != null)）
• 你可能要循環，直到n爲空，直到n.next爲空，否則你會跳過最後一個元素
• 要檢查n.val == val不n.next.val == val，否則你會跳過第一個元素
• 如果你檢查n，如果您需要刪除n，即prev.next = n.next，您想跟蹤前一個節點。
• 如果要移除第一個元素（頭部），則需要替換頭部，即返回第二個元素（這可以通過檢查prev == null來完成，這將意味着n是當前頭部）。

Answer 2

正如托馬斯在第一點中所提到的那樣，您錯誤地寫了while循環。另外，因爲你有一個鏈表，所以你需要跟蹤前一個節點（托馬斯也提到過）。

public static ListNode removeElements(ListNode head, int val) 
{ 
    ListNode n = head; 
    ListNode prev = null; //the previous node. 
    while (n != null) 
    { 
     if (n.value == val) 
     { 
      //if prev is null it means that we have to delete the head 
      //and therefore we need to advance the head 
      if (prev == null) 
      { 
       head = n.next; 
       prev = null;//remains at null because there's nothing before head 
       n = head;//new head, let's start from here 
      } else 
      { 
       prev.next = n.next; //let's skip the element to delete 
       n = n.next;//let's advance to the next node 
      } 
     } else 
     { 
      //nothing to delete, let's advance to the next node and make 
      //the current node the previous node in the next iteration 
      prev = n; 
      n = n.next; 
     } 

    } 
    return head; 
} 

Answer 3

它總是一個很好的做法，用適當的測試案例來解決這些問題。設計可能的測試案例，包括角落案例。然後按照你的算法，看看它是否解決了測試用例的問題。編寫代碼並幹運行它，這將對代碼以及邏輯進行完整的檢查。

下面是這個問題的案例必須寫入測試用例。

1. 空列表，
2. 列表與一個元件和值等於要被刪除的值
3. 與一種元素列表和值不等於要被刪除
4. 列表有兩個值元素和第一個節點值等於要刪除的值
5. 包含兩個元素並且最後一個節點值等於要刪除的值的列表
6. 包含三個元素並且第一個節點值等於被刪除
7. 列表具有三個元件和第二節點值等於所述值被刪除
8. 列表具有三個元件和最後一個節點值等於要被刪除

下面的值是代碼針對在鏈表中刪除具有給定值的節點的問題。

public ListNode removeElements(ListNode head, int val) { 
     while(head != null && head.val == val){ 
      head = head.next; 
     } 
     if(head == null){ 
      return null; 
     } 
     ListNode node = head; 
     while(node.next != null){ 
      if(node.next.val == val){ 
       node.next = node.next.next; 
      }else{ 
       node = node.next; 
      } 
     } 
     return head; 
}