c# - 面试题: remove duplicates from an unsorted linked list

Question

我正在阅读 Cracking the Coding Interview, Fourth Edition: 150 Programming Interview Questions and Solutions我正在尝试解决以下问题:

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

我正在用 C# 解决它，所以我制作了自己的 Node 类:

public class Node<T> where T : class
{
    public Node<T> Next { get; set; }
    public T Value { get; set; }

    public Node(T value)
    {
        Next = null;
        Value = value;
    }
}

我的解决方案是遍历列表，然后针对每个节点遍历列表的其余部分并删除所有重复项(请注意，我没有按照书中的说明实际编译或测试它):

public void RemoveDuplicates(Node<T> head)
{
    // Iterate through the list
    Node<T> iter = head;
    while(iter != null)
    {
        // Iterate to the remaining nodes in the list
        Node<T> current = iter;
        while(current!= null && current.Next != null)
        {
            if(iter.Value == current.Next.Value)
            {
                current.Next = current.Next.Next;
            }

            current = current.Next;
        }    

        iter = iter.Next;
    }
}

这是书中的解决方案(作者用java写的):

Without a buffer, we can iterate with two pointers: “current” does a normal iteration, while “runner” iterates through all prior nodes to check for dups. Runner will only see one dup per node, because if there were multiple duplicates they would have been removed already.

public static void deleteDups2(LinkedListNode head) 
{
    if (head == null) return;

    LinkedListNode previous = head;
    LinkedListNode current = previous.next;

    while (current != null) 
    {
        LinkedListNode runner = head;

        while (runner != current) { // Check for earlier dups
            if (runner.data == current.data) 
            {
                LinkedListNode tmp = current.next; // remove current
                previous.next = tmp;
                current = tmp; // update current to next node
                break; // all other dups have already been removed
            }
            runner = runner.next;
        }
        if (runner == current) { // current not updated - update now
            previous = current;
            current = current.next;
        }
    }
}

所以我的解决方案总是从当前节点到末尾查找重复项，而他们的解决方案从头部到当前节点查找重复项。我觉得这两种解决方案都会遇到性能问题，具体取决于列表中有多少重复项以及它们的分布方式(密度和位置)。但总的来说:我的答案和书中的答案差不多好还是差得多？

Answer 1

如果你给一个人一条鱼，他们会吃一天。授人以渔...

我对实现质量的衡量标准是:

• 正确性:如果您没有在所有情况下都得到正确的答案，那么它还没有准备好
• 可读性/可维护性:查看代码重复、可理解的名称、每个 block /方法的代码行数(以及每个 block 所做的事情的数量)以及跟踪的难度你的代码流。如果您想了解更多这方面的信息，请阅读许多侧重于重构、编程最佳实践、编码标准等方面的书籍。
• 理论性能(最坏情况和摊销):Big-O是您可以使用的指标。 CPU 和内存消耗都应该测量
• 复杂性:估计普通专业程序员需要如何实现(如果他们已经知道算法)。看看这是否符合问题的实际难度

至于您的实现:

• 正确性:我建议编写单元测试来自行确定这一点和/或使用有趣的示例/边缘案例从头到尾调试它(在纸上)。空、一项、两项、各种重复项等
• 可读性/可维护性:它看起来基本没问题，尽管您的最后两条评论没有添加任何内容。你的代码做了什么比书上的代码更明显一点
• 性能:我相信两者都是 N 平方的。摊销成本是哪一个更低，我会让你弄清楚:)
• 实现时间:普通专业人员应该能够在睡梦中编写此算法，看起来不错