การแสดงรายการเชื่อมโยงของตัวเลขมีให้ในลักษณะที่โหนดทั้งหมดของรายการที่เชื่อมโยงถือเป็นตัวเลขหนึ่งหลัก โหนดเก็บตัวเลขดังกล่าวเพื่อให้องค์ประกอบแรกของรายการที่เชื่อมโยงถือหลักที่สำคัญที่สุดของตัวเลข และองค์ประกอบสุดท้ายของรายการที่เชื่อมโยงเก็บบิตที่มีนัยสำคัญน้อยที่สุดของตัวเลข ตัวอย่างเช่น หมายเลข 202345 จะแสดงในรายการที่เชื่อมโยงเป็น (2->0->2->3->4->5)
และในการเพิ่มหมายเลขที่แสดงในรายการที่เชื่อมโยงนี้ เราต้องตรวจสอบค่าของบิตที่มีนัยสำคัญน้อยที่สุดของรายการ หากน้อยกว่า 9 ก็ไม่เป็นไร มิฉะนั้นรหัสจะเปลี่ยนหลักถัดไปเป็นต้น
ตอนนี้มาดูตัวอย่างเพื่อทราบวิธีการทำ 1999 แสดงเป็น (1-> 9-> 9 -> 9) และการเพิ่ม 1 เข้าไปควรเปลี่ยนเป็น (2->0->0->0)
Input:1999 Output:2000
คำอธิบาย
การเพิ่ม 1 ให้กับหมายเลขที่กำหนดซึ่งแสดงเป็นรายการเชื่อมโยงหมายถึงทำตามขั้นตอนบางอย่างนั่นคือ
- การย้อนกลับของรายการที่เชื่อมโยง:คุณต้องย้อนกลับรายการที่เชื่อมโยง ซึ่งหมายถึงการเปลี่ยนหลักสุดท้ายเป็นตัวแรกและตัวแรกเป็นตัวเลขสุดท้าย ตัวอย่างเช่น 1-> 9-> 9 -> 9 จะถูกแปลงเป็น 9-> 9 -> 9 ->1
- สำหรับรายการที่เชื่อมโยงที่เปลี่ยนแปลงนี้ ให้ข้ามรายการในโหนดด้านซ้ายสุด เพิ่มหนึ่งรายการ หากค่าของโหนดนี้เท่ากับ 9 ให้ส่งต่อไปยังโหนดถัดไป ทำขั้นตอนเดียวกันจนกว่าจะถึงเวลาพกพา
- ย้อนกลับสตริงกลับในรูปแบบเดิมแล้วคืนส่วนหัวเพื่อพิมพ์สตริง
ตัวอย่าง
#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;
} 