链表 - 在 C#/Java 中删除重复算法

Question

我正在学习 C# 中的数据结构和算法/Java。遇到LinkedList去重问题的解决方案后，一直纠结不解

解决方案是著名书籍 破解编码面试（第 5 版，第 208 页）中提出的解决方案。

void RemoveDuplicates_HashSet(Node n)
{
    HashSet<object> set = new HashSet<object>();

    Node previous = null;
    while (n != null)
    {
        if (set.Contains(n.Data))       // Condition 1
            previous.Next = n.Next;
        else                            // Condition 2
        {
            set.Add(n.Data);
            previous = n;
        }
            
        n = n.Next;
    }
}

运行链表如下代码A->B->A->B:

// Creating test Singly LinkedList
Node n = new Node("A");
n.Next = new Node("B");
n.Next.Next = new Node("A");
n.Next.Next.Next = new Node("B");

RemoveDuplicates_HashSet(n);

工作得很好：方法后 n 的值为 A->B.

通过使用调试器跟踪代码，我可以看到方法循环中发生的情况如下：

| Pass | HashSet | n          | previous   | Comment                  |
| ---- | ------- | ---------- | ---------- | ------------------------ |
| –    | –       | A->B->A->B | null       |                          |
| 1    | A       | B->A->B    | A->B->A->B | Condition 2 is triggered |
| 2    | A,B     | A->B       | B->A->B    | Condition 2 is triggered |
| 3    | A,B     | B          | B->B       | Condition 1 is triggered |
| 4    | A,B     | null       | B          | Condition 1 is triggered |

我无法理解这实际上是如何以多种方式产生的：

Where/how 确实从 n 中删除了重复项？我知道 HashSet 只包含独特的元素，因此它会检测是否已经遇到了一个元素，但是我仍然看不出算法是如何工作的。
怎么把n指向的值更新为A->B？鉴于本质上循环只是在执行 n = n.Next 的链接列表上迭代，n 实际上更新为最终值 A->B，它在哪里？我知道该列表是通过引用传递的，但我看不到它实际上是如何修改的。

Answer 1

Where/how exactly are duplicates dropped from n?

一个属性的 Set if，它不能包含重复的元素。

if (set.Contains(n.Data))
            previous.Next = n.Next;
else
{
            set.Add(n.Data);
            previous = n;
}
n = n.Next;

这里先检查一下，集合中是否包含当前节点n的数据。如果是，则前一个节点的后继者就是当前节点的下一个节点n。所以：

[previous]->[n]->[next]
[previous]->[next]

否则，数据被添加到集合中，您继续下一个节点。

How is it that the values pointed to by n are updated to be A->B? Where is it that, given that essentially the loop is simply iterating over the Linked List doing n = n.Next, n is actually updated with the final value A->B?

这个问题我真的不懂。你的意思是“为什么修改列表？” 如果是，那么因为它是通过引用传递的（有点 simplified ）。所以你只是不做复制，就像原始类型（int，long，...）一样，而是修改对象本身。

Answer 2

指出了我认为正确的方向。

问题 2) 的关键 - 更改实际上是如何从方法传播到原始列表的 - 理解 C#/Java objects are passed by reference, but the reference itself is passed by value: while the object can be modified by the method, the reference cannot be modified.
一旦方法结束（方法上下文终止），n 指针将再次指向链表的开始。在方法内不断推进 n 指针（通过做 n = n.Next）不会影响“外部指针”（方法外的原始 n 引用）。
根据问题 1) - 算法的内部机制 - 关键是理解修改 previous.Next 确实修改了 n 指向的列表。引用 :

This code: if (set.Contains(n.Data)) previous.Next = n.Next checks if the element has already been encountered and, if it has, removes n from the linked list. It removes the node by assigning n.Next to previous.Next (which means previous.Next no longer points to n).

因此，我试图详尽地描绘算法中发生的事情。

链表 - 在 C#/Java 中删除重复算法

Linked List - remove duplicates algorithm in C#/Java

c#

java

algorithm

linked-list

pass-by-reference