Tăng 1 cho số được biểu diễn dưới dạng danh sách liên kết

Ở đây chúng ta sẽ xem cách cộng 1 với một số được lưu trữ trong danh sách liên kết. Trong danh sách liên kết, mỗi chữ số của số được lưu trữ. Nếu số là 512, nó sẽ được lưu trữ như sau:

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

Chúng ta cung cấp danh sách cho hàm increment. Hàm sẽ trả về một danh sách khác sau khi cộng 1 vào nó. Ở đây chúng ta sử dụng danh sách liên kết STL của C++. Hãy xem thuật toán để hiểu rõ hơn.

Thuật toán

incrementList(l1)

Begin
  carry := 1
  res := một danh sách rỗng
  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; //1 này sẽ được cộng
  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);
}

Kết quả

The number: 9999
Result: 10000