这个 Java 代码是如何工作的？从未排序的链表中删除重复项

Question

我有一个链表节点class：

public static class Node {
    int value;
    Node next;

    Node(int value){
        this.value = value;
        this.next = null;
    }
}

以及删除重复项的方法：

public static void deleteDups(Node n) {
    Hashtable<Integer, Boolean> table = new Hashtable<Integer, Boolean>();
    Node previous = null;
    while (n != null) {
        if (table.containsKey(n.value)) previous.next = n.next;
        else {
            table.put(n.value, true);
            previous = n;
        }
        n = n.next;
    }
    }

public static void printList(Node list) {
    Node currentNode = list;
    while(currentNode != null) {
        System.out.print(currentNode.value + ", ");
        currentNode = currentNode.next;
    }
    System.out.println("");

}

有效。但是怎么办？在我删除列表 n 的方法中，最后 n 为空。但为什么这里不为空：

Node list = new Node(5);
list.next = new Node(2);
list.next.next = new Node(3);
list.next.next.next = new Node(2);
list.next.next.next.next = new Node(1);
list.next.next.next.next.next = new Node(3);

printList(list);    
deleteDups(list);
printList(list);

输出：

5, 2, 3, 2, 1, 3
5, 2, 3, 1

我错过了什么？

如果我打印 n 和前一个：

  public static void deleteDups(Node n) {
    Hashtable<Integer, Boolean> table = new Hashtable<Integer, Boolean>();
    Node previous = null;
    while (n != null) {
        if (table.containsKey(n.value)) previous.next = n.next;
        else {
            table.put(n.value, true);
            previous = n;
        }
        n = n.next;

        System.out.println("");
        System.out.println("");
        System.out.print("previous is ");
        printList(previous);            
        System.out.print("n is ");
        printList(n);
    }
    }

输出为：

previous is 5, 2, 3, 2, 1, 3, 
n is 2, 3, 2, 1, 3, 


previous is 2, 3, 2, 1, 3, 
n is 3, 2, 1, 3, 


previous is 3, 2, 1, 3, 
n is 2, 1, 3, 


previous is 3, 1, 3, 
n is 1, 3, 


previous is 1, 3, 
n is 3, 


previous is 1, 
n is

最后n和previous都为null！那么它是如何工作的？

Answer 1

简单地说，它迭代 linked 列表并记住它遇到的每个值。如果它遇到一个它已经看到的值，它会通过连接前一个节点（它在重复之前遇到的那个）和下一个（重复一个之后的那个）来断开链中的重复条目。

想象一下，它就像从链条中取出一个 link。

整个算法就地运行，因此之后无需重新创建列表。您只需丢弃不再需要的节点。

这有点危险，因为可能仍然有对不属于已过滤 linked 列表的节点的引用。最好以某种方式使它们无效。

另一方面，节点 next 属性将始终导致过滤后的节点 linked 列表（在 n 步之后）如果列表中仍有值算法如果重复节点已经位于 linked 列表的末尾，则尚未看到或 null。尽管如此，next 节点在再次到达作为重复自由 linked 列表的一部分的节点之前仍然会有重复项，但可以更改算法，这样即使这种情况也不会发生。

编辑以回答为什么 printList 什么都不打印/null 最后：

这是因为此时 n 不再是您的起始节点，它始终是 "next" 节点。所以最后 n 实际上是 "null" 因为 "null" 是最后一个节点之后的元素。您必须保留起始节点 n（您传递给 deleteDups 方法的节点，因为该节点描述了过滤列表的起始节点。您的 printList 方法仅打印您传递给它的节点之后的所有下一个节点。所以发生的最后一次调用是您的 printList(previous) （它包含最后一个元素）和 printList(n) 什么都不做，因为此时 n 是 "null"。

只需尝试创建一个 linked 节点列表。然后将第一个节点传递给 deleteDups，然后使用传递给它的节点调用 printList。

 Node start = new Node(...);

 //Initialize and connect more nodes consecutively here

 printList(start); //unfiltered List will be printed     
 deleteDups(start);
 printList(start); //filtered List will be printed, all duplicates have been unhinged from your linked list

Answer 2

列表是 "re-created"，其中：previous.next = n.next; 节点已更改，要跳过的项目已通过此操作删除

2 --> 3 --> 2
previous.next = n.next;
2 --------> 2

这个 Java 代码是如何工作的？从未排序的链表中删除重复项

How this Java code works? Remove duplicates from an unsorted linked list

java

linked-list