删除链接列表中的重复值（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中的递归）

回答

相关问题