从链接列表中删除重复项。为什么"prev = head"和"p2 = p2.next"的位置不在else语句之外？

Question

对于第一个函数，“prev = head”不应该在else之外，因为我们想在每次更改head值之前设置previous吗？

对于第二个函数，“p2 = p2.next”不应该在else之外，因为我们每次都想下一个吗？

谢谢大家


    //This would take O(n) but would require extra space O(n)
    public static Node removeDuplicates(Node head){
        Node prev = null;
        Set<Integer> hs = new HashSet<Integer>();
        
        while(head!= null){
            if(hs.contains(head.data)){
                prev.next = head.next;
            }
            else{
                hs.add(head.data);
                //why is prev = head here instead of out of the else statement? 
                prev = head;
            }
            head = head.next;
        }
        return head;
    }

    //This would take O(n^2) but no extra space is required.
    public static Node removeDuplicatesTradeOff(Node head){
        //pointer 1 and pointer 2.
        Node p1 = head;

        while(p1.next != null){
            Node p2 = p1;
            while(p2.next != null){
                if(p1.data == p2.next.data){
                    p2.next = p2.next.next;
                }
                else{
                    //why is p2 = p2.next here instead of out of the else statement? 
                    p2 = p2.next;
                }  
            }
            p1 = p1.next;
        }

        return head;
    }

Answer 1

使用解决方案 1 作为参考，因为答案适用于两种解决方案。当您在当前节点 (head) 找到重复项时，您将前一个节点的 (prev) next 节点设置为当前节点的 next 节点（这会删除重复项).在下一次迭代中，您将转到列表中的下一个节点，该节点已被前一个节点指向。所以，没有必要覆盖prev。另一种思考方式是，您要设置 prev 的 head 是您刚刚删除的节点。你不会想那样做的。

删除前：节点 1（上一个）-> 节点 2（头）-> 节点 3

删除后： node1 (prev) -> node3 (head)

如您所见，prev 保持不变。不用更新了。

Answer 2

Shouldn't "p2 = p2.next" be outside of else because we want to go next every time

我认为更准确的说法是我们想每次都有不同的下一个可用，而不是说我们每次都想“下一步”。

我们并不总是想“下一步”。当 prev.next 由于另一个操作（在这种情况下删除重复项）而改变时，我们希望保持原样，因为 prev.next 已经改变并且现在指向更远的节点（因为刚刚删除了重复节点）。

换句话说，我们不想每次都有不同的prev，我们只想每次都有不同的prev.next。所以只要 prev.next 每次都进步，我们不关心 prev 有时是否保持不变。

这就是为什么在这两种方法中prev（或p2）只在else分支中前进，而prev.next（或p2.next）被更新（预付款）仅在 if 分支中。

将这两个视为不同的操作，else 分支是“go next”，if 分支是“drop next”。当你在你前面放下一个节点时，你没有移动（真的！），但是因为你确实在你前面放下了一个节点，现在你前面有一个新节点，所以不必移动。所以你可以继续 if/else 检查，迟早你会到达终点，或者你会放弃你前面的最后一个节点。

一个说明这一点的输入例子是

head(1) -> 1 -> 1 -> 1 -> null

有了这样的输入，算法只会做

下一个
下一个
下一个

它会完成的。

根本没有发生“下一步”。

结果

head(1) -> null

Answer 3

removeDuplicates:

如果我们删除重复项，当前删除的节点应该而不是分配给prev。事实上 prev 是保留的唯一列表中的前一个节点。

很明显，当重复值超过 2 个时。

... -> prev: [42] -> [42] -> [42] -> [51] -> ...

应该变成

... -> prev: [42] -> [51] -> ...

删除重复权衡：

同样的情况。 p2（前一个节点）只有在没有找到重复项时才能前进。

然后有个小bug：

removeDuplicates 通常应该 return 新的 head - 以防头节点被移除：

head = remove...(head); // Must assign, should the head node itself be removed.

现在 returns null。但是对于重复项，永远不会删除头节点。因此，要么将其设为 void 函数，要么将其设为 return 旧的 head.

public static Node removeDuplicates(Node head){
    Node prev = null;
    Set<Integer> hs = new HashSet<>();

    Node current = head;
    // Loop-invariant: hs.isEmpty() || prev != null
    while (current != null) {
        if (hs.contains(current.data)) {
            prev.next = current.next;
        } else {
            hs.add(current.data);
            prev = current;
        }
        current = current.next;
    }
    return head;
}

另请注意，将名称 head 用于运行指针是一种糟糕的风格。

从链接列表中删除重复项。为什么"prev = head"和"p2 = p2.next"的位置不在else语句之外？

Removing Duplicates from linked list. Why are the position of "prev = head" and "p2 = p2.next" not outside the else statement?

java

linked-list

singly-linked-list