82. Remove Duplicates from Sorted List II

leetcode medium

#backtracking#csharp#leetcode#linked-list#medium#sort

Task

Дана голова отсортированного связного списка. Удалите все узлы, содержащие повторяющиеся числа, оставив только уникальные числа из исходного списка. Верните отсортированный связный список.

Пример:

Input: head = [1,2,3,3,4,4,5]

Output: [1,2,5]

C# solution

matched/original

public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        ListNode sentinel = new ListNode(0, head);
        ListNode pred = sentinel;
        while (head != null) {
            if (head.next != null && head.val == head.next.val) {
                while (head.next != null && head.val == head.next.val) {
                    head = head.next;
                }
                pred.next = head.next;
            } else {
                pred = pred.next;
            }
            head = head.next;
        }
        return sentinel.next;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public ListNode DeleteDuplicates(ListNode head) {
        ListNode sentinel = new ListNode(0, head);
        ListNode pred = sentinel;
        while (head != null) {
            if (head.next != null && head.val == head.next.val) {
                while (head.next != null && head.val == head.next.val) {
                    head = head.next;
                }
                pred.next = head.next;
            } else {
                pred = pred.next;
            }
            head = head.next;
        }
        return sentinel.next;
    }
}

Java solution

matched/original

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode sentinel = new ListNode(0, head);
        ListNode pred = sentinel;

        while (head != null) {
            if (head.next != null && head.val == head.next.val) {
                while (head.next != null && head.val == head.next.val) {
                    head = head.next;
                }
                pred.next = head.next;
            } else {
                pred = pred.next;
            }
            head = head.next;
        }
        return sentinel.next;
    }
}

JavaScript solution

matched/original

var deleteDuplicates = function (head) {
    let sentinel = new ListNode(0, head);
    let pred = sentinel;
    while (head !== null) {
        if (head.next !== null && head.val === head.next.val) {
            while (head.next !== null && head.val === head.next.val) {
                head = head.next;
            }
            pred.next = head.next;
        } else {
            pred = pred.next;
        }
        head = head.next;
    }
    return sentinel.next;
};

Python solution

matched/original

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        sentinel = ListNode(0, head)
        pred = sentinel

        while head:
            if head.next and head.val == head.next.val:
                while head.next and head.val == head.next.val:
                    head = head.next
                pred.next = head.next
            else:
                pred = pred.next
            head = head.next

        return sentinel.next

Go solution

matched/original

func deleteDuplicates(head *ListNode) *ListNode {
    sentinel := &ListNode{0, head}
    pred := sentinel
    for head != nil {
        if head.Next != nil && head.Val == head.Next.Val {
            for head.Next != nil && head.Val == head.Next.Val {
                head = head.Next
            }
            pred.Next = head.Next
        } else {
            pred = pred.Next
        }
        head = head.Next
    }
    return sentinel.Next
}

Explanation

Algorithm

1️⃣

Инициализация "стража" и предшественника:

Создается фиктивный начальный узел sentinel, который указывает на начало связного списка. Это делается для удобства управления указателем на начало списка, особенно если первые несколько узлов могут быть удалены.

Устанавливаем предшественника pred, который будет последним узлом перед потенциально дублирующимися узлами. Изначально предшественником назначается страж.

2️⃣

Проход по списку с проверкой на дубликаты:

Итерируемся по списку начиная с головы head. На каждом шаге проверяем, есть ли дублирующиеся узлы, сравнивая текущий узел head.val с следующим head.next.val.

Если узлы дублируются, то пропускаем все последующие дубликаты, перемещая указатель head до последнего дублированного узла. После этого предшественник pred соединяется с первым узлом после всех дубликатов

pred.next

head.next

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

3️⃣

Переход к следующему узлу и возврат результата:

Если текущий узел не имел дубликатов, просто переводим предшественника pred на следующий узел.

Двигаем указатель head на следующий узел в списке.

После завершения цикла возвращаем список, начиная с узла, на который указывает

sentinel.next

, что позволяет исключить все дублирующиеся узлы и вернуть начало нового списка без дубликатов.

😎