从未排序的链表中删除重复项，破解编码面试

Question

我正在通读这本书Cracking the coding interview by Gayle Mcdowell，并遇到了针对第 2 节链表上一个问题的替代解决方案。特别是问题#2.1

删除重复项：编写代码以从未排序的链表中删除重复项。如果不允许临时缓冲区，您将如何解决此问题。

Example input  = [1,2,2,6,4,4,2] 
Example output = [1,2,6,4]

作者在书中给出的答案如下：基本上，它保持"指针"，一个通过链表进行交互，另一个检查所有后续节点是否存在重复项：

    public void deleteDups(Node head) {
    Node current = head;
    while (current != null) {
        Node runner = current;
        while (runner.next != null) {
            if (runner.next.data == current.data) {
                runner.next = runner.next.next;
            } else {
                runner = runner.next;
            }
        }
        current = current.next;
    }
}

我使用了递归，我的代码看起来有点不同，尽管（我相信）做同样的事情：

public void removeRepetites(Node head) {
    if (head == null) return;
    int dataToRemove = head.data;
    while (head.next != null) {
        if (head.next.data == dataToRemove) {
            head.next = head.next.next;
        } else {
            removeRepetites(head.next);
            head = head.next;
        }
    }
}

你能发现我解决问题的方法有什么缺点吗？，也许是更高的空间/时间复杂度？

谢谢！

Answer 1

您的代码将如何处理包含 1,000,000 个唯一项的列表？

假设没有编译器或运行时优化，您的代码将堆栈溢出。

这就是为什么尾递归更好地优化为循环的原因。如果你这样做了，我想，它看起来像书中的答案。

Answer 2

就复杂性而言，在我看来，这两种实现都会导致 O（n^2） 复杂性，因为迭代答案涉及嵌套循环，而您的答案涉及在循环执行 n 次的循环中递归调用 n 次的函数。

我发现您的唯一问题/缺点是，由于它是递归的，由于对函数的递归调用，它将更快地填充堆栈空间。每次调用该函数时，它都会创建一个指向堆栈中函数的指针以及 dataToRemove 变量。

Answer 3

如果您的列表未排序，则两种解决方案都不起作用，它们仅比较相邻的值。我能想到的唯一解决方案是非常低效的性能明智 O（N^2）。循环访问列表并删除每个节点，然后检查列表是否包含等于已删除注释的节点并删除它们，然后重新插入已删除的节点。