Thêm 1 vào một số được biểu thị dưới dạng danh sách liên kết?

Ở đây chúng ta sẽ thấy cách thêm 1 với một số được lưu trữ vào danh sách liên kết. Trong danh sách liên kết, từng chữ số của các số được lưu trữ. Nếu số là 512, thì nó sẽ được lưu trữ như bên dưới -

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

Chúng tôi đang cung cấp danh sách vào chức năng tăng dần. Điều đó sẽ trả về một danh sách khác sau khi thêm 1 với nó. Ở đây chúng tôi đang sử dụng danh sách liên kết C ++ STL. Hãy để chúng tôi xem thuật toán để đặt cược ý tưởng tốt hơn.

Thuật toán

incrementList (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

Ví dụ

#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);
}

Đầu ra

The number: 9999
Result: 10000