c-删除链接列表中的重复项

Question

我看过、写过并测试过一些逻辑来删除链表中的重复项。例如，使用两个循环(O(n2))，或者在不保持顺序的情况下对重复项进行排序和删除
我只是想知道，如果我们提取链表的元素，并开始创建它们的二进制搜索树，使用二进制树算法中的标准重复检测来检测重复，这是否有效或清晰
这会比现有的逻辑更有效率，还是更糟？

Answer 1

您可以在O(n)时间内使用O(n)额外内存来完成此操作。这比BST方法更好：

1. 分配一个布尔值数组，大小为n，将所有单元格初始化为false
2. 遍历链接列表：
   • 对于每个节点，将值散列/映射到数组中的唯一索引中
   • 将单元格值设置为true
3. 创建指向新列表的指针
4. 遍历原始列表：
   • 对于每个节点，将值散列/映射到数组中的唯一索引中
   • 如果单元格值为true，则将节点添加到新列表中
   • 将单元格值设置为false
5. 将旧列表标题设置为新列表标题，然后删除旧列表标题

Answer 2

您的二进制搜索树（BST）替代方案会更快。让我们做一些分析：

1. 实例化BST对象O(1)
2. 使用链接列表N * O(log(N))中的每个节点填充BST
   注意作为插入操作的一部分，重复项不会添加到树中
3. 从BST O(N)重建链接列表

删除重复项的BST方法在O(1)+O(N)+O(N*log(N)) =O(N*log(N))中运行

它需要更多的代码和更大的内存才能运行，但会在准线性时间中删除重复项。

Answer 3

最好的选择（fastern）是创建二进制树来查找重复项，但您需要更多的内存和代码。

在c#中，您有Dictionary，在c++中，我认为有任何库模板可以使用

Answer 4

这个解决方案解决了不允许额外内存的问题，并就地更改了链表。解决方案在C#中

public static void removeDuplicates(Node root) { 
        Node reset = root;
        Node current = null;
        Node previous = null;
        Hashtable h = new Hashtable();
        //initialize hash table to all 0 values
        while (root != null)
        {
            if(!h.ContainsKey(root.value))
                h.Add(root.value, 0);
            root = root.next;
        }
        root = reset;
        ///count the number of times an element appears
        while (root != null)
        {
            h[root.value] = int.Parse(h[root.value].ToString()) + 1;
            root = root.next;
        }
        root = reset;
        previous = root;
        current = previous.next;            
        while (current != null) {
            if (int.Parse(h[current.value].ToString())>1)
            {
                h[current.value] = int.Parse(h[current.value].ToString())-1;
                previous.next = current.next;
                current = current.next;
            }
            else {
                previous = previous.next;
                current = current.next;
            }
        }
      // print them for visibility purposes
        while (reset != null) {
            Console.Write(reset.value + "->");
            reset = reset.next;
        }
    }
 static void Main(string[] args)
    {
        Node one = new Node(1);
        Node two = new Node(1);
        Node three = new Node(1);
        Node four = new Node(2);
        Node five = new Node(2);
   RemoveDuplicates(one);
   }