leetcode-2 Add Two Numbers

2. Add Two Numbers

Description

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.

Analyse

用加法合并两个单链表

开始我想把l2合并到l1去，发现我搞不定，于是把l1 l2合并到一个新的链表中去，下面是第一个版本

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
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    if (! (l1 && l2))
    {
        return l1 ? l2: l1;
    }

    int carry = 0;

    ListNode* root = new ListNode(l1->val + l2->val);
    carry = root->val / 10;
    root->val %= 10;

    ListNode* l3 = root;

    l1 = l1->next;
    l2 = l2->next;

    while (l1 || l2)
    {
        int v1 = l1 ? l1->val : 0;
        int v2 = l2 ? l2->val : 0;

        ListNode* tmp = new ListNode(v1 + v2 + carry);
        carry = tmp->val / 10;
        tmp->val %= 10;
        root->next = tmp;
        root = root->next;

        l1 = l1 ? l1->next : NULL;
        l2 = l2 ? l2->next : NULL;
    }

    if (carry != 0) //l1 l2都没了，但有进位，需加一个ListNode
    {
        ListNode * tmp = new ListNode(1);
        root->next = tmp;
    }

    return l3;
}

我看了LeetCode上最好的那份代码，比我的好多了，于是新的代码如下（copy & paste）

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
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    int carry = 0;
    ListNode *root = nullptr, *l3 = nullptr;

    while (l1 || l2 || carry)
    {
        if (l1)
        {
            carry += l1->val;
            l1 = l1->next;
        }

        if (l2)
        {
            carry += l2->val;
            l2 = l2->next;
        }

        if (l3)
        {
            l3->next = new ListNode(carry % 10);
            l3 = l3->next;
        }
        else
        {
            root = new ListNode(carry % 10);
            l3 = root;
        }

        carry /= 10;
    }

    return root;
}