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

Question

我正在通读盖尔·麦克道尔 (Gayle Mcdowell) 的《破解编程面试》一书，并发现了针对第 2 节链接列表中的问题之一的替代解决方案。具体来说就是问题#2.1

Remove dups: Write code to remove duplicates from an unsorted linked list. How would you solve this problem if a temporary buffer is not allowed.

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;
        }
    }
}

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

谢谢!

Answer 1

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

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

这就是尾递归更好地优化为循环的原因。我想，如果你当时这么做了，那就像是书中的答案。