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

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

}

第页。S-我不想返回删除的节点，我想返回新的头，我只想了解这背后的逻辑。

Answer 1

使用一个更简单的示例，您就会理解。考虑一个只有2个节点的列表。

1  -> 1*
^
Head

(*表示视觉区别(

您创建一个新的虚拟节点并将其指向Head

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

然后，您从dummy开始迭代(通过执行n = dummy(

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

输入循环，然后输入if条件。事实上，您正在更改n的next，也会更改dummy的next。

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

这样，只要连续值相同，就可以继续移动dummy的next。一旦遇到不同的值，则将n向前行进，并使dummy.next指向头部。

Answer 2

从未排序列表中删除重复节点：https://github.com/jayesh-tanna/coding-problem-solution/blob/master/DataStructures/SinglyLinkList/RemoveDuplicateNodesFromUnsortedList.java

从排序列表中删除重复项：https://github.com/jayesh-tanna/coding-problem-solution/blob/master/DataStructures/SinglyLinkList/RemoveDuplicatesFromSortedList.java