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

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

https://t.me/pythonl

Сложность: Средняя

Условие задачи: дается указатель на начало отсортированного связного списка, необходимо удалить все дублируемые значения в списке. Надо вернуть связный список, также отсортированный. 

Пример:

Ввод: head = [1,2,3,3,4,4,5]

Вывод: [1,2,5]

Ввод: head = [1,1,1,2,3]

Вывод: [2,3]


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:

        dummy = ListNode(None, None)
        dummy.next = head
        prev = dummy
        cur = head
        while cur and cur.next:

            if cur.next.val == cur.val:
                while cur.next and cur.next.val == cur.val:
                    cur = cur.next
                cur.next, cur = None, cur.next
                prev.next = cur
            else:
                prev = cur
                cur = cur.next

        return dummy.next


Report Page