题目链接: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
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
class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        if(l1 == NULL)
            return l2;
        if(l2 == NULL)
            return l1;
        
        ListNode *p1 = l1, *p2 = l2;
        while(p1 -> next != NULL && p2 -> next != NULL)
        {
            p1 -> val += p2 -> val;
            
            p1 = p1 -> next;
            p2 = p2 -> next;
        }
        p1 -> val += p2 -> val;
        
        if(p1 -> next == NULL)
            p1 -> next = p2 -> next;
        
        int a, c = 0;
        ListNode *p = l1;
        while(p -> next != NULL)
        {
            a = p -> val + c;
            p -> val = a % 10;
            c = a / 10;
            
            p = p -> next;
        }
        a = p -> val + c;
        p -> val = a % 10;
        c = a / 10;
        
        if(c == 1)
        {
            ListNode *pln = new ListNode(1);
            p -> next = pln;
        }
        
        return l1;
    }
};

上面代码太长了。。。下面在两个链表对应节点相加的时候,同时用变量c维护进位,这样1次循环就都搞定了。

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
class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode *h = new ListNode(0), *cur = h;
        int c = 0;
        while(l1 != NULL || l2 != NULL)
        {
            int a1 = l1 != NULL ? l1 -> val : 0;
            int a2 = l2 != NULL ? l2 -> val : 0;
            int a = a1 + a2 + c;
            c = a / 10;
            cur -> next = new ListNode(a % 10);
            cur = cur -> next;
            if(l1 != NULL)
                l1 = l1 -> next;
            if(l2 != NULL)
                l2 = l2 -> next;
        }
        if(c > 0)
            cur -> next = new ListNode(c);
        return h -> next;
    }
};