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