Plus One Linked List - Cộng 1 vào số nguyên biểu diễn bằng danh sách liên kết

Cho số nguyên không âm biểu diễn bằng danh sách liên kết đơn (chữ số quan trọng nhất ở đầu). Cộng 1 vào số này. Giả sử không có số 0 đầu tiên trừ chính số 0.

Ví dụ: [1,2,3] → [1,2,4].

Giải thuật

Tìm nút cuối cùng không phải 9 (gọi là req). Nếu không có (tức tất cả đều là 9), tạo nút mới giá trị 1 làm đầu, đặt tất cả nút cũ thành 0. Ngược lại, tăng req lên 1, đặt tất cả nút sau req thành 0.

Cài đặt C++

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

class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int data) { val = data; next = NULL; }
};

ListNode* make_list(vector<int> v) {
    ListNode* head = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ListNode* ptr = head;
        while (ptr->next) ptr = ptr->next;
        ptr->next = new ListNode(v[i]);
    }
    return head;
}

void print_list(ListNode* head) {
    cout << "[";
    while (ptr) {
        cout << ptr->val << ", ";
        ptr = ptr->next;
    }
    cout << "]" << endl;
}

class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        if (!head) return head;
        ListNode* curr = head;
        ListNode* req = NULL;
        while (curr) {
            if (curr->val != 9) req = curr;
            curr = curr->next;
        }
        if (!req) {
            ListNode* dummy = new ListNode(1);
            dummy->next = head;
            while (head) {
                head->val = 0;
                head = head->next;
            }
            return dummy;
        } else {
            req->val++;
            req = req->next;
            while (req) {
                req->val = 0;
                req = req->next;
            }
            return head;
        }
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,4,5};
    ListNode* head = make_list(v);
    print_list(ob.plusOne(head));
    return 0;
}

Đầu vào

{1,4,5}

Đầu ra

[1, 4, 6, ]