-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path2.cpp
More file actions
70 lines (65 loc) · 1.85 KB
/
2.cpp
File metadata and controls
70 lines (65 loc) · 1.85 KB
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
/*************************************************************************
> File Name: 2.cpp
> Author: Alan
> Mail: [email protected]
> Created Time: Sun 08 Nov 2015 01:42:23 AM PST
> Problem Name: Add Two Numbers
> Difficulty: Medium
> Description:
You are given two linked lists representing two non-negative numbers. 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.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
************************************************************************/
#include<iostream>
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode head(-1);
ListNode* prev = &head, * p1, * p2;
int carry = 0, value;
for(p1 = l1, p2 = l2; p1 || p2; p1 = p1 ? p1->next : nullptr, p2 = p2 ? p2->next : nullptr, prev = prev->next)
{
const int num1 = p1 ? p1->val : 0;
const int num2 = p2 ? p2->val : 0;
value = (num1 + num2 + carry) % 10;
carry = (num1 + num2 + carry) / 10;
prev->next = new ListNode(value);
}
if(carry > 0)
{
prev->next = new ListNode(carry);
}
return head.next;
}
};
int main()
{
Solution sol = Solution();
ListNode l1(2), l11(4), l12(3), l2(5), l21(6), l22(4);
l1.next = &l11;
l11.next = &l12;
l2.next = &l21;
l21.next = &l22;
ListNode * result = sol.addTwoNumbers(&l1, &l2);
while(result)
{
cout << result->val;
if(result->next)
{
cout << "->";
}
result = result->next;
}
cout << endl;
}