leetcode2:两数相加

题目链接

leetcode

题目描述

给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。
假设除了数字 0 之外,这两个数都不会以 0 开头。

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <vector>
using namespace std;

// 链表结点的定义
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 辅助函数:创建链表
ListNode* createList(const vector<int>& nums) {
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
for (int num : nums) {
cur->next = new ListNode(num);
cur = cur->next;
}
return dummy->next;
}

// 辅助函数:打印链表
void printList(ListNode* head) {
while (head != nullptr) {
cout << head->val;
if (head->next != nullptr) cout << " -> ";
head = head->next;
}
cout << endl;
}

// 辅助函数:释放链表内存
void deleteList(ListNode* head) {
while (head != nullptr) {
ListNode* temp = head;
head = head->next;
delete temp;
}
}

/*
模拟列竖式做加法:
1.从最低位至最高位,逐位相加。
若和大于等于 10,则保留个位数字,同时向前一位进 1。
2.如果最高位有进位,则在最前面补 1。

有关链表的题目,常用技巧:
添加一个虚拟头结点,简化边界的判断。

时间复杂度:O(n)
其中 n 为链表的长度,遍历链表一次。
空间复杂度:O(1)
创建结果链表,注意返回值不计入空间复杂度。
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode();
ListNode* cur = dummy;
int carry = 0;

while (l1 || l2 || carry) {
int num1 = l1 ? l1->val : 0;
int num2 = l2 ? l2->val : 0;
int sum = num1 + num2 + carry;
// 处理进位
carry = sum / 10;
sum = sum % 10;
// 插入新结点
cur->next = new ListNode(sum);
cur = cur->next;
if (l1) {
l1 = l1->next;
}
if (l2) {
l2 = l2->next;
}
}

return dummy->next;
}
};

int main() {
Solution solution;
vector<vector<vector<int>>> lists_cases = {
{{2,4,3}, {5,6,4}},
{{0}, {0}},
{{9,9,9,9,9,9,9}, {9,9,9,9}},
};

for (size_t i = 0; i < lists_cases.size(); i++) {
// 创建链表
ListNode* l1 = createList(lists_cases[i][0]);
ListNode* l2 = createList(lists_cases[i][1]);
cout << "Input: " << endl;
printList(l1);
printList(l2);

// 相加操作
ListNode* result = solution.addTwoNumbers(l1, l2);
cout << "Output: " << endl;
printList(result);

// 释放内存
deleteList(l1);
deleteList(l2);
deleteList(result);
}

return 0;
}

leetcode2:两数相加
https://lcf163.github.io/2023/08/07/leetcode2:两数相加/
作者
乘风的小站
发布于
2023年8月7日
许可协议