java - 删除链表中的重复值(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

首先，您的代码仅解决列表是否有序的问题，如果数据位于随机位置，则无法删除所有重复节点，例如:1, 2, 3, 1, 1, 2, 3

其次，为了你的关心，你可以这样想:

案例一:

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

在列表末尾之前检查from元素，将其数据与下一个数据进行比较，如果匹配，则将下一个节点替换为下一个下一个节点。然后，跳转到上一个节点并重复。

案例二:

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

您从第一个节点开始，检查它是否与下一个节点重复。如果重复，则用第 3 个节点替换第 2 个节点。然后，跳转到下一个节点(现在是原来的第3个节点)，检查是否复制到下一个节点。你看，你错过了检查第 1 个节点和原来的第 3 个节点。

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

顺便说一句，尝试将约定应用于您的代码。杰希望对您有所帮助!