首页 > 代码库 > LeetCode --- 2. Add Two Numbers
LeetCode --- 2. Add Two Numbers
题目链接：Add Two Numbers
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
这道题的要求是将用链表表示的两个数（数字以相反顺序存储）相加，并返回加和之后的链表。
思路是首先将第二个链表的每个节点加到第一个链表对应的节点上（当然新建链表节点也可以），然后如果第二个链表有剩余，就将其全部加到第一个链表后面。最后再依次处理进位。值得注意的是最后的进位哦。。。
时间复杂度：O(n)
空间复杂度：O(1)
1 class Solution
2 {
3 public:
4 ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
5 {
6 if(l1 == NULL)
7 return l2;
8 if(l2 == NULL)
9 return l1;
10
11 ListNode *p1 = l1, *p2 = l2;
12 while(p1 -> next != NULL && p2 -> next != NULL)
13 {
14 p1 -> val += p2 -> val;
15
16 p1 = p1 -> next;
17 p2 = p2 -> next;
18 }
19 p1 -> val += p2 -> val;
20
21 if(p1 -> next == NULL)
22 p1 -> next = p2 -> next;
23
24 int a, c = 0;
25 ListNode *p = l1;
26 while(p -> next != NULL)
27 {
28 a = p -> val + c;
29 p -> val = a % 10;
30 c = a / 10;
31
32 p = p -> next;
33 }
34 a = p -> val + c;
35 p -> val = a % 10;
36 c = a / 10;
37
38 if(c == 1)
39 {
40 ListNode *pln = new ListNode(1);
41 p -> next = pln;
42 }
43
44 return l1;
45 }
46 };上面代码太长了。。。下面在两个链表对应节点相加的时候，同时用变量c维护进位，这样1次循环就都搞定了。
1 class Solution
2 {
3 public:
4 ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
5 {
6 ListNode *h = new ListNode(0), *cur = h;
7 int c = 0;
8 while(l1 != NULL || l2 != NULL)
9 {
10 int a1 = l1 != NULL ? l1 -> val : 0;
11 int a2 = l2 != NULL ? l2 -> val : 0;
12 int a = a1 + a2 + c;
13 c = a / 10;
14 cur -> next = new ListNode(a % 10);
15 cur = cur -> next;
16 if(l1 != NULL)
17 l1 = l1 -> next;
18 if(l2 != NULL)
19 l2 = l2 -> next;
20 }
21 if(c > 0)
22 cur -> next = new ListNode(c);
23 return h -> next;
24 }
25 };转载请说明出处：LeetCode --- 2. Add Two Numbers
LeetCode --- 2. Add Two Numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。