資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學將用連結串列表示的數字加 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。
- 對於此更改後的連結串列，現在遍歷連結串列，在最左邊的節點上加一。如果該節點的值等於 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;
}
更新於：2019年8月19日
530 次瀏覽
廣告