链表中重复节点的删除

Question

从链表中删除所有重复节点的程序如下。在代码中，我们是 return 链表删除后的新头部 "dummy.next" 但是在开始时虚拟指向头部所以如果我们删除头部，那么 dummy.next 也应该 return 删除的节点那为什么是returning 新的头？输入示例：1 1 1 2 3 Output: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- 我不想 return 删除的节点，我想要 return 新的头部，我只是想了解这背后的逻辑。

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

链表中重复节点的删除

Deletion of duplicate node in Linked List

algorithm

linked-list

data-structures

singly-linked-list