链表实际上是如何改变的

Question

我想知道是否有人可以帮助我解决这个问题。我相信我大部分都理解代码和逻辑。我可以跟踪代码，这是有道理的，但我不明白的一件事是......前面的 LinkedListNode 实际上如何更改传入的 LinkedListNode n ？

在我看来，该函数循环遍历 n，如果尚未找到该元素，则将其放入哈希表中。但是当再次找到它时，它使用这个新创建的 LinkedListNode previous 来跳过重复项并链接到后面的元素，即 n.next。 这实际上是如何断开 LinkedListNode n 的呢？看起来 previous 是没有重复项的 LinkedListNode，但由于此函数中没有返回任何内容，因此 n 必须是发生更改的那个。我想我没有看到 n 实际上是如何改变的。

清晰彻底的帮助将不胜感激。谢谢 = )

public static void deleteDups(LinkedListNode n){

    Hashtable table = new Hashtable();
    LinkedListNode previous = null;
    while(n != null){
        if(table.containsKey(n.data))
            previous.next = n.next
        else{
            table.put(n.data, true);
            previous = n;
        }
        n = n.next;
    }
}

这行不是

LinkedListNode previous = null;

创建一个新的 LinkedListNode 吗？

所以这就是我的逻辑... 假设参数 n 作为

5 -> 传入6-> 5-> 7

当代码第一次运行时，previous为null。它进入 else 语句，而 previous 现在是 5？然后 n = n.next 行使 n 为 6？现在哈希表有 5，它再次循环并进入 else。 prev 现在是 6，hastable 有 6。然后 n 变成 5。它再次循环，但这次它进入 if，prev 现在是 7。n 将变成 7。我看到 prev 跳过了 5，但是.. .prev 如何取消链接 n？看起来 prev 是不包含重复项的 LinkedListNode

Answer 1

之前的 LinkedListNode 实际上是如何改变的
传入的LinkedListNode n？

看线

n = n.下一个；

该行导致传递的节点 n 发生变化 - 在每次迭代中有效地将其向前移动一个节点。

它使用这个新创建的 LinkedListNode 来跳过重复项并链接到以下元素

不，这里没有新创建节点。节点previous总是指向现有LinkedList中的一个节点，其中传递的节点n是该节点之一。 （可能是起始节点）。是什么让您认为它是新创建的？

看起来您对节点和引用（以及整个 LinkedList）如何在 Java 中工作的理解感到困惑。因为所有修改都发生在 Node 的数据上，而不是引用本身（呃..这并不完全正确），所以传递给该方法的原始 LinkedList 在该方​​法返回后确实会被修改。您需要详细分析 LinkedList 结构和工作原理以了解其工作原理。我建议首先弄清楚 Java 中的值传递和引用传递是什么。

编辑：

您对运行的分析是正确的，但是您的困惑仍然存在，因为您在某些事情上概念上不清楚。

在分析结束时，您会问“..prev 如何取消链接 n？似乎 prev 是 LinkedListNode< /code> 不包含重复项“

这是一团糟 - 首先，您需要区分 LinkedListNode 和 LinkedList 本身。 prev 和 n 是 LinkedListNode 的两个实例，而不是 LinkedList 本身。在您的示例中，LinkedList 未命名（我们没有一个名称来引用它）。这是原始列​​表 - 没有其他列表。

其次，在你的插图中，你显示的数字只是节点的一部分，称为节点数据。您错过的另一部分是每个节点中隐含的 next LinkedListNode 引用。您绘制的链接 ->实际上是每个节点中的下一个引用。当您说 prev 跳过 5 时，实际发生的情况是数据为 6 的节点的下一个指向数据为 7 的节点。

在开始时：
5|下一个 -> 6|下一个 -> 5|下一个 -> 7|next->NULL

跳过 5 后：
5|下一个 -> 6|下一个 -> 7|next->NULL

如您所见，链表已更改！无论是使用 prev 还是 n 进行更改，更改都会保留在列表中。

Answer 2

if(table.containsKey(n.data))
            previous.next = n.next

是进行删除的部分。它将前一个节点的 next 字段的引用分配给当前节点之后的节点，实际上取消了当前节点的链接。