删除链表中的重复值（Java中的递归）

Question

我需要返回链接列表的头部，删除所有重复的元素。我理解问题的逻辑，但我在使用递归时感到困惑

/*
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'.

我真的想要一些关于如何更好地理解递归的建议

Answer 1

问题是，在后一种情况下，您“跳过”了一些节点。 让我们命名示例中的节点，看看发生了什么：

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

切换行时不会出现此问题，因为这样您就走另一条路，即从下到上（从右到左）浏览列表，并且只向右比较/删除（“在您后面”的行走方向）

Answer 2

首先，您的代码只在列表有序时才进行求解，如果数据处于随机位置，则无法删除所有重复的节点，例如：1, 2, 3, 1, 1, 2, 3

其次，对于您的关注，您可以这样想：

案例1：

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

您可以在列表末尾之前检查from元素，比较其数据和下一个数据，如果匹配，则用下一个节点替换下一个节点。然后，跳到上一个节点并重复

案例2：

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

从第一个节点开始，检查它是否与下一个节点重复。如果重复，则使用第三个节点替换第二个节点。跳转到下一个节点（现在是原始的第三个节点）以检查它是否复制到下一个节点。你看，你没有检查第一个节点和原来的第三个节点

我认为您应该尝试调试模式来深入了解这一点

顺便说一句，尝试将约定应用于代码。J 希望这有帮助