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

Question

我有一个LinkedList节点类:

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

和delete duplicate方法:

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为空。但是为什么这里不是null呢:

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和前面都是空的!那么它是如何工作的呢?

Answer 1

简单地说，它迭代链表并记住它遇到的每个值。如果它遇到一个它已经见过的值，它就通过连接前一个节点(在重复之前遇到的节点)和下一个节点(在重复之后的节点)来中断链中的重复条目。

就把它想象成从链条上取下一个链环。

整个算法在原位工作，因此之后不需要重新创建列表。你只需要扔掉那些不再需要的节点。

这有点危险，因为仍然可能存在对不再属于过滤链表的节点的引用。最好以某种方式让它们失效。

另一方面，如果列表中仍有一个值算法尚未看到，则节点的next属性将始终导致过滤链表的节点(经过n步)，或者如果重复节点已经在链表的末尾，则导致null。尽管如此，next节点仍然会有重复的，直到它到达一个节点，这个节点是重复的自由链表的一部分，但是可以改变算法，这样即使这样也不会发生。

编辑以回答为什么printList在末尾不打印/null:

这是因为n在这一点上不再是你的开始节点，它总是"下一个"节点。所以最后n实际上是"null"因为"null"是最后一个节点之后的元素。必须保留起始节点n(传递给deletedup方法的节点n)，因为该节点描述过滤列表的起始节点。printList方法只打印传递给它的节点之后的所有下一个节点。所以最后调用的是printList(previous)(它包含最后一个元素)和printList(n)，它什么都不做，因为此时n为"null"。

尝试创建节点的链表。然后将第一个Node传递给deleteDups，然后使用传递给它的Node调用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

列表被"重新创建"为:previous.next = n.next;修改节点，并使用以下操作删除要跳过的项

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