Удаление дубликата узла в связанном списке

Question

Программа для удаления всех повторяющихся узлов из связанного списка написана ниже. В коде мы возвращаем новый заголовок связанного списка после удаления как «dummy.next», но при запуске dummy указывает на заголовок, поэтому, если мы удаляем head, то 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;
}

}

PS - я не хочу возвращать удаленный узел, я хочу вернуть новую голову, и я просто хочу понять логику c за этим.

Answer 1

Удалить дубликаты узлов из несортированного списка: 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

Answer 2

Работайте с более простым примером, и вы поймете. Рассмотрим список с двумя узлами.

1  -> 1*
^
Head

(* означает визуальное различие)

Вы создаете новый фиктивный узел и указываете его рядом с заголовком

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

Затем вы начинаете итерацию с пустышки (выполняя n = dummy)

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

Вы вводите l oop и вводите условие if. Тот факт, что вы меняете n next, также меняет dummy * next.

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

Таким образом, вы продолжаете двигаться dummy * next до тех пор, пока последовательные значения одинаковы. Как только вы встретите другое значение, вы идете вперед n и оставляете dummy.next, указывая на голову.