Tambahkan 1 pada nombor yang diwakili oleh senarai terpaut

Perwakilan senarai terpaut bagi nombor disediakan seperti ini: Semua nod senarai terpaut dianggap sebagai satu digit nombor. Nod menyimpan nombor supaya elemen pertama senarai terpaut memegang digit paling ketara bagi nombor itu, dan elemen terakhir senarai terpaut memegang digit nombor paling ketara. Sebagai contoh, nombor 202345 diwakili dalam senarai terpaut sebagai (2->0->2->3->4->5).

Untuk menambah 1 pada senarai terpaut ini yang mewakili nombor, kita perlu menyemak nilai bit paling tidak ketara dalam senarai. Jika kurang daripada 9 tidak mengapa, jika tidak kod akan menukar nombor seterusnya dan seterusnya.

Sekarang mari kita lihat contoh untuk memahami cara melakukan ini, 1999 diwakili sebagai (1->9->9 ->9) dan menambah 1 harus menukarnya kepada (2->0->0->0 )

Input:1999
Output:2000

Penjelasan

Tambahkan 1 pada nombor yang diwakili oleh senarai terpaut yang diberikan, bermakna anda perlu mengikuti langkah berikut:

• Terbalikkan senarai terpaut: Anda perlu membalikkan senarai terpaut, iaitu menukar yang terakhir nombor kepada yang pertama, Yang pertama menjadi yang terakhir. Contohnya, 1->9->9->9 diterjemahkan kepada 9->9->9->1.
• Untuk senarai terpaut terbalik ini, lewati senarai terpaut dan tambah 1 pada nod paling kiri. Jika nilai nod itu bersamaan dengan 9, maka pembawa dihantar ke nod seterusnya. Ulangi proses ini sehingga tiada pembawa.
• Pulihkan rentetan kepada bentuk asalnya dan kembalikan nod kepala untuk mencetak rentetan.

Contoh

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

Atas ialah kandungan terperinci Tambahkan 1 pada nombor yang diwakili oleh senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!