將一個以鍊錶表示的數字加1

數字的鍊錶表示是這樣提供的：鍊錶的所有節點都被視為數字的一位數字。節點儲存數字，使得鍊錶的第一個元素保存數字的最高有效位，鍊錶的最後一個元素保存數字的最低有效位。例如，數字 202345 在鍊錶中表示為 (2->0->2->3->4->5)。

要為這個表示數字的鍊錶加 1，我們必須檢查清單中最低有效位的值。如果小於 9 就可以了，否則程式碼將更改下一個數字，依此類推。

現在讓我們看一個範例來了解如何做到這一點，1999 表示為(1-> 9- > 9 -> 9) 並添加1 應該將其更改為(2->0-> 0->0)

Input:1999
Output:2000

解釋

將給定的鍊錶表示的數字加1，意味著需要按照以下步驟進行操作：

• 反轉鍊錶：需要將鍊錶反轉，即將最後一個數字變成第一個，第一個變成最後一個。例如，1-> 9-> 9 -> 9 轉換為 9-> 9 -> 9 ->1。
• 對於這個反轉後的鍊錶，遍歷鍊錶，在最左邊的節點上加1。如果該節點的值等於9，則將進位傳遞到下一個節點。重複這個過程，直到沒有進位。
• 將字串還原為原始形式，然後傳回頭節點以列印字串。

範例

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

以上是將一個以鍊錶表示的數字加1的詳細內容。更多資訊請關注PHP中文網其他相關文章！