删除链接列表中的重复节点。

Question

下面是删除链接列表中所有重复节点的程序。在这段代码中，我们以 "dummy.next "的形式返回删除后的链接列表的新头，但是在开始时，dummy是指向头的，所以如果我们删除了头，那么dummy.next也应该返回被删除的节点，那么为什么它要返回新的头呢？ 示例输入：1 1 1 2 3 输出：2 3

class Solution {
public ListNode deleteDuplicates(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode n = dummy;
    while (n.next != null && n.next.next != null) {
        if (n.next.val == n.next.next.val) {
            int duplicate = n.next.val;
            while (n.next != null && n.next.val == duplicate) {
                n.next = n.next.next;
            }
        } else {
            n = n.next;
        }
    }
    return dummy.next;
}

}

P.S-我不想返回被删除的节点，我想返回新的头部，我只是想了解这背后的逻辑。

Answer 1

用一个更简单的例子工作，你就会明白。考虑一个只有2个节点的列表。

1  -> 1*
^
Head

(* 是表示视觉上的区别)

你创建了一个新的虚拟节点，并将其指向Head的旁边。

0  ->  1  ->  1*
^      ^
dummy  Head

然后，你从dummy开始迭代（通过做 n = dummy)

0    ->  1  ->  1*
^        ^    
n,dummy  Head

你进入循环，进入if条件。事实上，你正在改变 n's next，也有变化 dummy's next.

0    ->  1*  <- 1
^               ^
n,dummy         Head

这样一来，你就可以继续前进 dummy's next 只要连续的数值相同就可以了。一旦遇到不同的值，那么你就会行进。n 前行而去 dummy.next 指向头部。

Answer 2

从未排序列表中删除重复节点。https:/github.comjayesh-tannacoding-problem-solutionblobmasterDataStructuresSinglyLinkListRemoveDuplicateNodesFromUnsortedList.java。

从排序列表中删除重复的内容。https:/github.comjayesh-tannacoding-problem-solutionblobmasterDataStructuresSinglyLinkListRemoveDuplicatesFromSortedList.java。