Сложность: hard
Дано неотрицательное целое число, представленное в виде связного списка цифр. Добавить к этому числу единицу.
Цифры хранятся таким образом, что самая значимая цифра находится в начале списка.
Пример:
Input: head = [1,2,3]
Output: [1,2,4]
👨💻 Алгоритм:
1️⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову списка: sentinel.next = head. Найдите крайний правый элемент, не равный девяти.
2️⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль.
3️⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next).
😎 Решение:
class Solution:
def plusOne(self, head: ListNode) -> ListNode:
# sentinel head
sentinel = ListNode(0)
sentinel.next = head
not_nine = sentinel
# find the rightmost not-nine digit
while head:
if head.val != 9:
not_nine = head
head = head.next
# increase this rightmost not-nine digit by 1
not_nine.val += 1
not_nine = not_nine.next
# set all the following nines to zeros
while not_nine:
not_nine.val = 0
not_nine = not_nine.next
return sentinel if sentinel.val else sentinel.next
Ставь 👍 и забирай 📚 Базу знаний