เพิ่ม 1 ให้กับตัวเลขที่แสดงเป็นรายการที่เชื่อมโยงหรือไม่

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

512 = (5)-->(1)-->(2)-->NULL

เรากำลังจัดเตรียมรายการลงในฟังก์ชันการเพิ่มขึ้น ที่จะกลับรายการอื่นหลังจากเพิ่ม 1 กับมัน ที่นี่เราใช้รายการเชื่อมโยง C++ STL มาดูอัลกอริทึมกันดีกว่า

อัลกอริทึม

รายการที่เพิ่มขึ้น(l1)

Begin
   carry := 1
   res := an 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

ตัวอย่าง

#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; //this 1 will be added
   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