從已排序的鏈接列表中刪除重複的節點。爲什麼我的輸出錯誤？

Question

給定一個有序鏈接列表，刪除所有具有重複號碼的節點，只保留原始列表中不同的數字。

例子：

• 鑑於1->2->3->3->4->4->5->null，返回1->2->5->null。

• 鑑於1->1->1->2->3->null，返回2->3->null。

問題：

• 鑑於1->1->1->2->3->null，下面return 3->null

我的解決方案誰能告訴我爲什麼？

/** 
* Definition for ListNode 
* public class ListNode { 
*  int val; 
*  ListNode next; 
*  ListNode(int x) { 
*   val = x; 
*   next = null; 
*  } 
* } 
*/ 
public class Solution { 
    /** 
    * @param ListNode head is the head of the linked list 
    * @return: ListNode head of the linked list 
    */ 
    public static ListNode deleteDuplicates(ListNode head) { 
     // write your code here 
     if(head == null || head.next == null) return head; 

     ListNode post = head.next; 
     ListNode curr = head; 
     ListNode dummy = new ListNode(head.val-1); // make sure dummy node value is different from the head 
     dummy.next = head; 
     ListNode prev = dummy; 

     while(post != null) { 
      //System.out.println("prev.val = " + prev.val + ", curr.val = " + curr.val + ", post.val = " + post.val + ", prev.next.val = " + prev.next.val); 
      //System.out.println("prev.next.val = " + prev.next.val + ", curr.next.val = " + curr.next.val);    

      if(prev.next.val == curr.val && prev.next.val == post.val) { 
       curr = curr.next; 
       post = post.next; 
      } 
      else if(prev.next.val == curr.val && prev.next.val != post.val) { 
       curr = curr.next; 
       post = post.next;     
       prev.next = curr; 
      } 
      else { 
       prev = prev.next; 
       curr = curr.next; 
       post = post.next; 
      } 
     } 

     return dummy.next; 
    } 
} 

Answer 1

不改變你的程序在做什麼， 的while循環可轉化爲這種更可讀的形式：

while (post != null) { 
    if (prev.next.val != curr.val || prev.next.val != post.val) { 
     if (prev.next.val == curr.val) { 
      prev.next = curr.next; 
     } else { 
      prev = prev.next; 
     } 
    } 
    curr = curr.next; 
    post = post.next; 
} 

這等同於您的實際代碼。 我會根據這個版本， 解釋，因爲我覺得這更容易閱讀和推理。

讓我們看到幾件事情：

• 在開始的時候，prev.next點curr。因此prev.next.val等於curr.val。 另外，post比curr提前一步。

• curr與post一起移動。 curr和post在if條件 內部沒有更改，並且作爲循環的最後一步， 它們都向前推進一個位置。

給定了輸入1，1，1，2，3，和上述觀察：

• 外if條件將是假的，直到達到post 2.

• curr是後面一步，所以它指向1之前的那個。

• prev沒有移動，所以prev.next仍然指向前1。

• 所以在這一點上，prev.next.val等於curr.val（均爲1）， 但它不等於post.val，這是2 所以我們進入外，如果。

• 作爲prev.next.val == curr.val，我們還輸入內部if, 並設置prev.next = curr.next。 請記住，循環的最後一步將推進curr至curr.next。 因此prev.next將指向curr。

• 在下一次迭代中，我們有post在3，curr在2和prev.next指向curr。所以我們進入其他if，然後內if，設置prev.next到curr.next，這是3

這是結束。 prev從未移動過，它留在原來的位置，即dummy。 prev.next指向3，我們返回，不正確。 注意，如果輸入是更長，例如1，1，1，2，3，4，5，6， 相同的行爲將繼續， prev.next以下curr， 和實施將錯誤地返回6 -> null。 該算法已損壞。

---

考慮這樣的替換算法：

1. 創建一個虛擬節點，指向head在明年（因爲你已經做了）
2. 將當前節點接到虛
3. 雖然下一個節點存在，並且存在下一個下一個節點
   • 比較next.val和next.next.val
   • 如果不相等，然後推進當前節點
   • 如果相等，則：
     • 保存的next.val
     • 一個複製跳過next和next.next（旁邊設置爲next.next.next）
     • 跳過所有進一步其值等於保存的節點val
4. 返回dummy.next

像這樣：

if (head == null) return head; 

ListNode dummy = new ListNode(head.val - 1); 
dummy.next = head; 

ListNode node = dummy; 
while (node.next != null && node.next.next != null) { 
    if (node.next.val != node.next.next.val) { 
     node = node.next; 
    } else { 
     int val = node.next.val; 
     node.next = node.next.next.next; 
     while (node.next != null && node.next.val == val) { 
      node.next = node.next.next; 
     } 
    } 
} 

return dummy.next;