给定由两个列表表示的两个数字，编写一个返回总和列表的函数。总和列表是两个输入数字相加的列表表示。
示例：
输入：
List1: 5->6->3 // 代表数字 563
List2: 8->4->2 // 代表数字 842
输出：
结果列表：1->4->0->5 // 代表数字 1405
解释： 563 + 842 = 1405
输入：
List1: 7->5->9->4->6 // 代表数字 75946
List2: 8->4 // 代表数字 84
输出：
结果列表：7->6->0->3-> 0// 代表数字 76030
解释： 75946+84=76030
方法：从末尾遍历两个列表，并一一选择两个列表的节点并添加值。如果总和大于 10，则进位为 1 并减少总和。如果一个列表的元素多于另一个，则将此列表的剩余值视为 0。反转最终列表以获得总和。
步骤是：
- 从头到尾遍历两个链表。
- 分别从各自的链表中添加两位数字。
- 如果其中一个列表已到达末尾，则取 0 作为其数字。
- 继续它直到列表的末尾。
- 如果两位数之和大于 9，则将进位设置为 1，将当前位数设置为和 % 10反转结果列表以获得实际和。
下面是这个方法的实现。
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; Node* newNode(int data) { Node* new_node = new Node(); new_node->data = data; new_node->next = NULL; return new_node; } void push(Node** head_ref, int new_data) { Node* new_node = newNode(new_data); new_node->next = (*head_ref); (*head_ref) = new_node; } Node* addTwoLists(Node* first, Node* second) { Node* res = NULL; Node *temp, *prev = NULL; int carry = 0, sum; while (first != NULL || second != NULL) { sum = carry + (first ? first->data : 0) + (second ? second->data : 0); carry = (sum >= 10) ? 1 : 0; sum = sum % 10; temp = newNode(sum); if (res == NULL) res = temp; else prev->next = temp; prev = temp; if (first) first = first->next; if (second) second = second->next; } if (carry > 0) temp->next = newNode(carry); return res; } Node* reverse(Node* head) { if (head == NULL || head->next == NULL) return head; Node* rest = reverse(head->next); head->next->next = head; head->next = NULL; return rest; } void printList(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } cout << endl; } int main(void) { Node* res = NULL; Node* first = NULL; Node* second = NULL; push(&first, 6); push(&first, 4); push(&first, 9); push(&first, 5); push(&first, 7); printf("First List is "); printList(first); push(&second, 4); push(&second, 8); cout << "Second List is "; printList(second); first = reverse(first); second = reverse(second); res = addTwoLists(first, second); res = reverse(res); cout << "Resultant list is "; printList(res); return 0; }
输出
First List is 7 5 9 4 6 Second List is 8 4 Resultant list is 5 0 0 5 6
复杂度分析：
- 时间复杂度： O(m + n)，其中 m 和 n 分别是第一个和第二个列表中的节点数。
列表只需要遍历一次。 - 空间复杂度： O(m + n)。
需要一个临时链表来存储输出编号
方法二（Using STL）： 使用栈数据结构
方法 ：
- 创建 3 个堆栈，即 s1、s2、s3。
- 用 list1 的节点填充 s1，用 list2 的节点填充 s2。
- 通过创建新节点并将新节点的数据设置为 s1.top()、s2.top() 的总和来填充 s3，并进位直到 list1 和 list2 为空。
- 如果总和 >9
- 设置进位 1
- 别的
- 设置进位 0
- 创建一个包含总和列表头部的节点（比如上一个）。
- 从上到下链接s3的所有元素
- 返回上一页
代码：
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; Node* newnode(int data) { Node* x = new Node(); x->data = data; return x; } Node* addTwoNumbers(Node* l1, Node* l2) { Node* prev = NULL; stack<Node*> s1, s2, s3; while (l1 != NULL) { s1.push(l1); l1 = l1->next; } while (l2 != NULL) { s2.push(l2); l2 = l2->next; } int carry = 0; while (!s1.empty() && !s2.empty()) { int sum = s1.top()->data + s2.top()->data + carry; Node* temp = newnode(sum % 10); s3.push(temp); if (sum > 9) { carry = 1; } else { carry = 0; } s1.pop(); s2.pop(); } while (!s1.empty()) { int sum = carry + s1.top()->data; Node* temp = newnode(sum % 10); s3.push(temp); if (sum > 9) { carry = 1; } else { carry = 0; } s1.pop(); } while (!s2.empty()) { int sum = carry + s2.top()->data; Node* temp = newnode(sum % 10); s3.push(temp); if (sum > 9) { carry = 1; } else { carry = 0; } s2.pop(); } if (carry == 1) { Node* temp = newnode(1); s3.push(temp); } if (!s3.empty()) prev = s3.top(); while (!s3.empty()) { Node* temp = s3.top(); s3.pop(); if (s3.size() == 0) { temp->next = NULL; } else { temp->next = s3.top(); } } return prev; } void Display(Node* head) { if (head == NULL) { return; } while (head->next != NULL) { cout << head->data << " -> "; head = head->next; } cout << head->data << endl; } void push(Node** head_ref, int d) { Node* new_node = newnode(d); new_node->next = NULL; if (*head_ref == NULL) { new_node->next = *head_ref; *head_ref = new_node; return; } Node* last = *head_ref; while (last->next != NULL && last != NULL) { last = last->next; } last->next = new_node; return; } int main() { Node* first = NULL; Node* second = NULL; Node* sum = NULL; push(&first, 9); push(&first, 5); push(&first, 0); push(&second, 6); push(&second, 7); cout << "First List : "; Display(first); cout << "Second List : "; Display(second); sum = addTwoNumbers(first, second); cout << "Sum List : "; Display(sum); return 0; }
输出
First List : 9 -> 5 -> 0 Second List : 6 -> 7 Sum List : 1 -> 0 -> 1 -> 7
另一种时间复杂度为 O(N) 的方法：
给定的方法按以下步骤工作：
- 首先，我们分别计算链表 size1 和 size2 的大小。
- 然后我们遍历更大的链表，如果有的话，递减直到两者的大小相同。
- 现在我们遍历两个链表直到结束。
- 现在在执行加法时发生回溯。
- 最后，返回包含答案的链表的头节点。
#include <iostream> using namespace std; struct Node { int data; struct Node* next; }; Node* addition(Node* temp1, Node* temp2, int size1, int size2) { Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (temp1->next == NULL && temp2->next == NULL) { newNode->data = (temp1->data + temp2->data); newNode->next = NULL; return newNode; } Node* returnedNode = (struct Node*)malloc(sizeof(struct Node)); if (size2 == size1) { returnedNode = addition(temp1->next, temp2->next, size1 - 1, size2 - 1); newNode->data = (temp1->data + temp2->data) + ((returnedNode->data) / 10); } else { returnedNode = addition(temp1, temp2->next, size1, size2 - 1); newNode->data = (temp2->data) + ((returnedNode->data) / 10); } returnedNode->data = (returnedNode->data) % 10; newNode->next = returnedNode; return newNode; } struct Node* addTwoLists(struct Node* head1, struct Node* head2) { struct Node *temp1, *temp2, *ans = NULL; temp1 = head1; temp2 = head2; int size1 = 0, size2 = 0; while (temp1 != NULL) { temp1 = temp1->next; size1++; } while (temp2 != NULL) { temp2 = temp2->next; size2++; } Node* returnedNode = (struct Node*)malloc(sizeof(struct Node)); if (size2 > size1) { returnedNode = addition(head1, head2, size1, size2); } else { returnedNode = addition(head2, head1, size2, size1); } if (returnedNode->data >= 10) { ans = (struct Node*)malloc(sizeof(struct Node)); ans->data = (returnedNode->data) / 10; returnedNode->data = returnedNode->data % 10; ans->next = returnedNode; } else ans = returnedNode; return ans; } void Display(Node* head) { if (head == NULL) { return; } while (head->next != NULL) { cout << head->data << " -> "; head = head->next; } cout << head->data << endl; } void push(Node** head_ref, int d) { Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = d; new_node->next = NULL; if (*head_ref == NULL) { new_node->next = *head_ref; *head_ref = new_node; return; } Node* last = *head_ref; while (last->next != NULL && last != NULL) { last = last->next; } last->next = new_node; return; } int main() { // Creating two lists Node* first = NULL; Node* second = NULL; Node* sum = NULL; push(&first, 5); push(&first, 6); push(&first, 3); push(&second, 8); push(&second, 4); push(&second, 2); cout << "First List : "; Display(first); cout << "Second List : "; Display(second); sum = addTwoLists(first, second); cout << "Sum List : "; Display(sum); return 0; }
输出
First List : 5 -> 6 -> 3 Second List : 8 -> 4 -> 2 Sum List : 1 -> 4 -> 0 -> 5
