c - 删除链表中的重复项

Question

我已经看到、编写和测试了一些逻辑来删除链表中的重复项。例如，使用两个循环，或者排序和删除重复项，尽管它不保留顺序。 我只是想知道如果我们拉出链表的元素并开始创建它们的二叉搜索树，它使用二叉树算法中的标准重复检测来检测重复，它是否有效或清晰。 这会比现有逻辑更有效，还是更糟？(O(n2))

Answer 1

您可以O(n)使用O(n)额外的内存及时完成。这比 BST 方法更好：

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

Answer 2

您的二叉搜索树(BST) 替代方案会更快。让我们做一些分析：

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

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

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

Answer 3

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

在c#中你有字典，在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);
   }