เพิ่ม 1 ให้กับตัวเลขที่เก็บใน Linked List

ที่นี่เราจะดูวิธีการบวก 1 กับตัวเลขที่เก็บอยู่ใน Linked List ใน Linked List แต่ละหลักของตัวเลขจะถูกเก็บไว้ ตัวอย่างเช่น ถ้าตัวเลขคือ 512 จะเก็บเป็นดังนี้

512 = (5)→(1)→(2)→NULL

เราจะส่ง Linked List เข้าไปในฟังก์ชัน increment ซึ่งจะคืนค่า Linked List ใหม่หลังจากบวก 1 แล้ว ที่นี่เราใช้ C++ STL Linked List มาดูอัลกอริทึมเพื่อความเข้าใจที่ดีขึ้น

อัลกอริทึม

incrementList(l1)

Begin
    carry := 1
    res := empty list
    for each node n from l1, scan from last to first, do
        item := (l1.item + carry) mod 10
        insert item at the beginning of res
        carry := (l1.item + carry) / 10
    done
    if carry is not 0 then
        add carry at the beginning of res
    end if
    return res
End

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <list>
using namespace std;

list<int> incListNum(list<int> l1) {
    list<int>::reverse_iterator it1 = l1.rbegin();
    list<int> result;
    int carry = 1; // 1 นี้จะถูกบวกเข้าไป
    while (it1 != l1.rend()) {
        result.push_front((*it1 + carry) % 10);
        carry = (*it1 + carry) / 10;
        it1++;
    }
    if (carry != 0) {
        result.push_front(carry);
    }
    return result;
}

list<int> numToList(int n) {
    list<int> numList;
    while (n != 0) {
        numList.push_front(n % 10);
        n /= 10;
    }
    return numList;
}

void displayListNum(list<int> numList) {
    for (list<int>::iterator it = numList.begin(); it != numList.end(); it++) {
        cout << *it;
    }
    cout << endl;
}

int main() {
    int n1 = 9999;
    list<int> n1_list = numToList(n1);
    list<int> res = incListNum(n1_list);
    cout << "The number: ";
    displayListNum(n1_list);
    cout << "Result: ";
    displayListNum(res);
}

ผลลัพธ์

The number: 9999
Result: 10000