刪除鏈接列表中的重複值（Java中的遞歸）

我需要返回鏈接列表的頭部，並刪除所有重複的元素。我理解問題的邏輯，但是我在使用遞歸時感到困惑。刪除鏈接列表中的重複值（Java中的遞歸）

/* 
Node is defined as 
class Node { 
    int data; 
    Node next; 
} 
*/ 

Node RemoveDuplicates(Node head) { 
    if ((head == null) || (head.next == null)) 
     return head; 
    else { 
     RemoveDuplicates(head.next); 
     if (head.data==head.next.data) head.next = head.next.next; 
    } 
    return head; 
}

如果我在if條件之前調用RemoveDuplicates（head.next）函數，它工作正常。然而，如果我交換語句的順序（休息一切是完全一樣的），如：

if (head.data==head.next.data) head.next = head.next.next; 
RemoveDuplicates(head.next);

的代碼無法正確地解決用於測試用例如「1-> 1-> 1-> 1」。我在後一種情況下得到的輸出是'1-> 1'。

我真的很想就如何更好地理解遞歸提出一些建議。

來源

2016-11-23 Ritika Jain

一些細節： - 你不需要在第一個括號中圍繞這兩個術語，因爲（'=='在'||'之前）[https://docs.oracle.com/javase/tutorial/的java/nutsandbolts/operators.html]。 - 按照慣例，Java中的方法沒有大寫，即在這種情況下它應該被命名爲'removeDuplicates'。 –

首先，你的代碼就只能解決如果列表中的命令，它不能刪除所有重複的節點，如果在任意位置的數據，例如：1, 2, 3, 1, 1, 2, 3

其次，你的關心，你可以認爲它像如下：

案例1：

您從元素右側的列表結束前檢查，比較其數據和下一個數據，如果匹配，通過接下來的下一個節點替換下一個節點。然後，跳轉到前一個節點並重復。

案例2：

if (head.data==head.next.data) head.next = head.next.next; 
RemoveDuplicates(head.next);

你開始的第一個節點，檢查它是否與下一個節點複製。如果重複，則將第3個節點替換爲第2個節點。跳轉到下一個節點（現在是第三個節點），檢查它是否複製到下一個節點。你看，你錯過了檢查第一個節點和原來的第三個節點。

我想你應該嘗試模式調試來深入瞭解這一點。

順便說一句，嘗試將慣例應用於您的代碼。 J 希望得到這個幫助！

來源

2016-11-23 08:43:08

問題在於你在後一種情況下「跳過」了一些節點。讓我們命名的節點在你的例子，看看發生了什麼：

v 
1 -> 1 -> 1 -> 1 
a b c d

v表示head在你的方法當前的參考。

如果你現在做一個檢查第一，你比較a和b，然後取出b：

v 
1 -> 1 -> 1 
a c d

然後你做一個遞歸步驟，其向前行進一個節點c：

問題是你在後一種情況下「跳過」一些節點。讓我們命名的節點在你的例子，看看發生了什麼：

v 
1 -> 1 -> 1 -> 1 
a b c d

v表示head在你的方法當前的參考。

如果你現在做一個檢查第一，你比較a和b，然後取出b：

 v 
1 -> 1 -> 1 
a c d

這裏是你的問題。您從未將c與其左側的值進行比較，即a/c或b/c。

切換線路時不會出現此問題，因爲您以其他方式行走，即從下往上（從右至左）通過您的列表並僅在右側進行比較/刪除（「後面你「在步行方向）。

來源

2016-11-23 08:38:10

刪除鏈接列表中的重複值（Java中的遞歸）

回答

相關問題