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

Question

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

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

谢谢你们。

    //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

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