2. Add Two Numbers (Medium)

You are given two **non-empty** linked lists representing two non-negative integers. The digits are stored in **reverse order** and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

**Example**

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
思路:同时遍历两个链表,将对应位相加,结果58ms,排名71.24%
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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(0), *p = dummy;
int carry = 0;
while(l1 || l2 || carry){
if(l1){
carry+=l1->val;
l1 = l1->next;
}
if(l2){
carry+=l2->val;
l2 = l2->next;
}
p->next = new ListNode(carry%10);
carry /= 10;
p = p->next;
}
return dummy->next;
}
};
看了一圈网上的题解,思路基本是这个套路。下面是leetcode官网最快的代码。(29ms),实际运行40ms,而如果没有static const auto段的话,反而更慢,只有80ms。
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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
static const auto _____ = []()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode(0);
ListNode* curr = head;
int cbit = 0;
int a = 0;
int b = 0;
while(l1||l2)
{
int sum = ((l1)?(l1->val):(0)) + ((l2)?(l2->val):(0)) + cbit;
curr->next = new ListNode(sum%10);
cbit = sum/10;
if(l1) l1 = l1->next;
if(l2) l2 = l2->next;
curr = curr->next;
}
if (cbit)
{
curr->next = new ListNode(cbit);
}
return head->next;
}
};
仔细观察,可以看到,该解法比第一种解法,少了进位的判断次数,但增加了l1和l2是否是Null的判断,因此算法写法上并不占便宜。我将蜜汁优化段加入到第一种解法中,显示运行时间40ms,排名99.08%!(另外,每次提交时,时间可能不同,这可能跟测试用例有关)
1
static const auto _____ = [](){ios::sync_with_stdio(false);cin.tie(nullptr);return nullptr;}();
解释: sync_with_stdio函数:是一个“是否兼容studio"的开关,C++为了兼容C,保证程序在使用了std::print和std::cout的时候不发生混乱,将输出流绑到了一起。首先sync_with_stdio(false)是为了打断iostream输入输出到缓存,可以节约很多时间,使之与scanf相差无几 tie是将两个stream绑定的函数,空参数的话返回当前的输出指针,即tie(0)与tie(nullptr)来解决cin与cout的绑定。