資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++實現兩數相加 II
假設我們有兩個非空的連結串列，分別表示兩個非負整數。這裡最高位數字排在最前，每個節點包含單個數字。我們需要將這兩個數字相加，並將其結果作為連結串列返回。例如，如果連結串列是 [7, 2, 4, 3] + [5, 6, 4]，則結果將是 [7, 8, 0, 7]
為了解決這個問題，我們將遵循以下步驟：
建立一個名為 dummy 的節點，並將其值儲存為 0，建立堆疊 s1 和 s2。
用 l1 的節點填充 s1，用 l2 的節點填充 s2。
sum := 0
當 s1 不為空或 s2 不為空時
如果 s1 為空，則 sum := sum + s1 的頂部值，從堆疊 s1 中刪除。
如果 s2 為空，則 sum := sum + s2 的頂部值，從堆疊 s2 中刪除。
dummy 的值 := sum mod 10
新節點 := 建立一個值為 sum/10 的新節點
新節點的 next := dummy
dummy := 新節點
sum := sum / 10
如果 dummy 的值為 0，則返回 dummy 的 next，否則返回 dummy。
示例 (C++)
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
void print_list(ListNode *head){
ListNode *ptr = head;
cout << "[";
while(ptr){
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << "]" << endl;
}
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy;
dummy = new ListNode(0);
stack <ListNode*> s1, s2;
while(l1){
s1.push(l1);
l1 = l1->next;
}
while(l2){
s2.push(l2);
l2 = l2->next;
}
int sum = 0;
while(!s1.empty() || !s2.empty()){
if(!s1.empty()){
sum += s1.top()->val;
s1.pop();
}
if(!s2.empty()){
sum += s2.top()->val;
s2.pop();
}
dummy->val = (sum % 10);
ListNode* newNode = new ListNode(sum / 10);
newNode->next = dummy;
dummy = newNode;
sum /= 10;
}
return dummy->val == 0? dummy->next : dummy;
}
};
main(){
vector<int> v1 = {7,2,4,3};
ListNode *h1 = make_list(v1);
vector<int> v2 = {5,6,4};
ListNode *h2 = make_list(v2);
Solution ob;
print_list(ob.addTwoNumbers(h1, h2));
}輸入
[7,2,4,3] [5,6,4]
輸出
[7, 8, 0, 7, ]
更新於：2020年5月2日
291 次瀏覽
廣告