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

Số được biểu diễn bằng danh sách liên kết: mỗi nút là một chữ số. Nút đầu tiên chứa chữ số quan trọng nhất, nút cuối chứa chữ số ít quan trọng nhất. Ví dụ 202345 biểu diễn là (2→0→2→3→4→5).

Để cộng 1, kiểm tra chữ số cuối. Nếu < 9 thì xong, ngược lại phải truyền nhớ sang chữ số trước. Ví dụ 1999 biểu diễn (1→9→9→9), cộng 1 thành (2→0→0→0).

Input:1999 Output:2000

Giải thích

Các bước cộng 1 vào số dạng danh sách liên kết:

• Đảo ngược danh sách: đổi chỗ chữ số cuối lên đầu. 1→9→9→9 thành 9→9→9→1.
• Duyệt danh sách đã đảo, tại nút đầu cộng 1. Nếu giá trị = 9 thì truyền nhớ sang nút tiếp. Lặp cho đến khi không còn nhớ.
• Đảo ngược lại về dạng ban đầu và trả về head để in.

Ví dụ

#include <iostream>
using namespace std;

// n=next node; d=data; p=previous node; h=head node; c=current node
class Node {
public:
    int d;
    Node* n;
};

Node *newNode(int d) {
    Node *new_node = new Node;
    new_node->d = d;
    new_node->n = NULL;
    return new_node;
}

Node *reverse(Node *h) {
    Node *p = NULL;
    Node *c = h;
    Node *n;
    while (c != NULL) {
        n = c->n;
        c->n = p;
        p = c;
        c = n;
    }
    return p;
}

Node *addOneUtil(Node *h) {
    Node* res = h;
    Node *temp, *p = NULL;
    int carry = 1, sum;
    while (h != NULL) {
        sum = carry + h->d;
        carry = (sum >= 10)? 1 : 0;
        sum = sum % 10;
        h->d = sum;
        temp = h;
        h = h->n;
    }
    if (carry > 0)
        temp->n = newNode(carry);
    return res;
}

Node* addOne(Node *h) {
    h = reverse(h);
    h = addOneUtil(h);
    return reverse(h);
}

int main() {
    Node *h = newNode(1);
    h->n = newNode(9);
    h->n->n = newNode(9);
    h->n->n->n = newNode(9);
    h = addOne(h);
    while (h != NULL) {
        cout << h->d;
        h = h->n;
    }
    cout<<endl;
    return 0;
}