为什么要保留“上一个”？删除链表中的重复项时？

Question

我想知道是否有人可以解释使用“LinkedListNode previous”变量的目的是什么。我了解尝试删除重复项的总体思路。您查看链表，如果某个值不在哈希表中，则将其插入。但如果是的话，它在做什么？我不太确定。

非常感谢您的帮助！如果有人能以清晰易懂的方式解释它，我将不胜感激。谢谢！

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;
    }
}

Answer 1

如果没有“前一个”，链表 cons 链如何保持连接？

想象一下：如果要将 Current 项变为 Prev->Current->Next，则需要将其转换为 Prev->Next从列表中删除。如果 Prev 没有临时保存，则无法对其进行突变以更新链接。 （如果列表是双向链接列表，则不需要 Prev 因为它可以从 Current->previous 恢复）。

快乐编码。

---

回应评论中的问题：

如果不采取任何措施，则重复项目不会从列表中断开连接。 n = n.next 更改 n 的值（但不会更改存储在 n 或其他位置的元素/节点的数据，因此 < code>Prev.next 从未从 Current 更改）。

需要做的是Prev的next，被删除元素之前的元素/节点，必须更新为引用已删除元素之后的元素 (Next)。

previous.next = n.next; // and this does it

（这也可以用函数式非突变风格编写，其中原始列表不会被修改，并且会构建一个新列表 - 在这种情况下，就不需要 Prev）。

Answer 2

public static void deleteDup( LinkedList* h){

    if( !h || !h->next )
        return;
    Hashtable ht = new Hashtable();
    LinkedListNode* previous = h;
    LinkedListNode* curr = h->next;
    while( curr ){
        if( ht.containsKey() ){
            previous->next = curr->next;
            free(curr);
            curr = previous->next;

        }
        else{
            ht.put(curr->data, true );
             previous = curr;
             curr = curr->next;
        }
    }
}