369. Plus One Linked List

LeetCode hard оригинал: C# #csharp #hard #leetcode #linked-list
LeetCode Static

Дано неотрицательное целое число, представленное в виде связного списка цифр. Добавить к этому числу единицу.

Цифры хранятся таким образом, что самая значимая цифра находится в начале списка.

Пример:

Input: head = [1,2,3]

Output: [1,2,4]

C# решение

сопоставлено/оригинал 
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}
public class Solution {
    public ListNode PlusOne(ListNode head) {
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
        ListNode notNine = sentinel;
        ListNode current = head;
        while (current != null) {
            if (current.val != 9) {
                notNine = current;
            }
            current = current.next;
        }
        notNine.val += 1;
        notNine = notNine.next;
        while (notNine != null) {
            notNine.val = 0;
            notNine = notNine.next;
        }
        return sentinel.val == 0 ? sentinel.next : sentinel;
    }
}

C++ решение

auto-draft, проверить перед отправкой 
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}
class Solution {
public:
    public ListNode PlusOne(ListNode head) {
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
        ListNode notNine = sentinel;
        ListNode current = head;
        while (current != null) {
            if (current.val != 9) {
                notNine = current;
            }
            current = current.next;
        }
        notNine.val += 1;
        notNine = notNine.next;
        while (notNine != null) {
            notNine.val = 0;
            notNine = notNine.next;
        }
        return sentinel.val == 0 ? sentinel.next : sentinel;
    }
}

Java решение

сопоставлено/оригинал 
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    public ListNode plusOne(ListNode head) {
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
        ListNode notNine = sentinel;

        ListNode current = head;
        while (current != null) {
            if (current.val != 9) {
                notNine = current;
            }
            current = current.next;
        }

        notNine.val += 1;
        notNine = notNine.next;

        while (notNine != null) {
            notNine.val = 0;
            notNine = notNine.next;
        }

        return sentinel.val == 0 ? sentinel.next : sentinel;
    }
}

JavaScript решение

сопоставлено/оригинал 
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    plusOne(head) {
        let sentinel = new ListNode(0);
        sentinel.next = head;
        let notNine = sentinel;

        let current = head;
        while (current !== null) {
            if (current.val !== 9) {
                notNine = current;
            }
            current = current.next;
        }

        notNine.val += 1;
        notNine = notNine.next;

        while (notNine !== null) {
            notNine.val = 0;
            notNine = notNine.next;
        }

        return sentinel.val === 0 ? sentinel.next : sentinel;
    }
}

Python решение

сопоставлено/оригинал 
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

Go решение

сопоставлено/оригинал 
package main

type ListNode struct {
    Val  int
    Next *ListNode
}

func plusOne(head *ListNode) *ListNode {
    sentinel := &ListNode{0, head}
    notNine := sentinel

    current := head
    for current != nil {
        if current.Val != 9 {
            notNine = current
        }
        current = current.Next
    }

    notNine.Val += 1
    notNine = notNine.Next

    for notNine != nil {
        notNine.Val = 0
        notNine = notNine.Next
    }

    if sentinel.Val == 0 {
        return sentinel.Next
    } else {
        return sentinel
    }
}

Algorithm

Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову списка:

sentinel.next

= head. Найдите крайний правый элемент, не равный девяти.

Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль.

Верните sentinel, если его значение было установлено на 1, иначе верните head (

sentinel.next

).

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии
Активных вакансий пока нет.