Biểu diễn danh sách liên kết của một số được cung cấp theo cách mà tất cả các nút của danh sách liên kết được coi là một chữ số của số. Nút lưu trữ số sao cho phần tử đầu tiên của danh sách được liên kết chứa chữ số quan trọng nhất của số và phần tử cuối cùng của danh sách được liên kết chứa bit quan trọng nhất của số. Ví dụ:số 202345 được biểu thị trong danh sách liên kết là (2-> 0-> 2-> 3-> 4-> 5).
Và để thêm một số vào danh sách được liên kết này, chúng ta phải kiểm tra giá trị của bit quan trọng nhất trong danh sách. Nếu nhỏ hơn 9 thì không sao, nếu không mã sẽ thay đổi chữ số tiếp theo, v.v.
Bây giờ chúng ta hãy xem một ví dụ để biết cách thực hiện, 1999 được biểu thị là (1-> 9-> 9 -> 9) và thêm 1 vào nó sẽ thay đổi nó thành (2-> 0-> 0-> 0)
Input:1999 Output:2000
Giải thích
Để thêm 1 vào một số nhất định được biểu thị dưới dạng danh sách liên kết, nghĩa là phải làm theo một số bước,
- đảo ngược danh sách được liên kết:bạn cần đảo ngược danh sách được liên kết, điều này có nghĩa là thay đổi chữ số cuối cùng thành chữ số đầu tiên và chữ số đầu tiên thành chữ số cuối cùng. Ví dụ:1-> 9-> 9 -> 9 được chuyển đổi thành 9-> 9 -> 9 -> 1.
- cho danh sách được liên kết đã thay đổi này bây giờ duyệt qua danh sách, trong nút ngoài cùng bên trái, hãy thêm một. nếu giá trị của nút này bằng 9 thì sẽ truyền tải cho Node tiếp theo. Thực hiện quy trình tương tự cho đến khi hoàn tất.
- đảo ngược chuỗi trở lại như ở dạng ban đầu và sau đó trả lại phần đầu để in chuỗi.
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;
}