AddTwoNumbers [source code]

public class AddTwoNumbers {
static
/******************************************************************************/
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null)
            return l2;
        else if (l2 == null)
            return l1;
        ListNode res = new ListNode ((l1.val + l2.val) % 10);
        ListNode res_head = res;
        int carry = (l1.val + l2.val) / 10;
        while (l1.next != null && l2.next != null) {
            l1 = l1.next;
            l2 = l2.next;
            res.next = new ListNode ((l1.val + l2.val + carry) % 10);
            carry = (l1.val + l2.val + carry) / 10;
            res = res.next;
        }
        ListNode rest = l1.next == null ? l2 : l1;
        while (rest.next != null) {
            rest = rest.next;
            res.next = new ListNode ((rest.val + carry) % 10);
            carry = (rest.val + carry) / 10;
            res = res.next;
        }
        if (carry > 0)
            res.next = new ListNode (1);
        return res_head;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        AddTwoNumbers.Solution tester = new AddTwoNumbers.Solution();
    }
}

看题目意思感觉不是很难, 因为顺序是从左到右从低到高, 不过既然标的是medium, 担心还是有可能有什么我不知道的坑, 先写再说;

pre-leaf termination for LinkedList

另外注意LinkedList题目很多时候循环的header用pre leaf判断好像比用leaf判断更方便, 不知道这里用不用得到这个技巧(原因是当你走到Null leaf的时候, 已经太晚了);

最后还算是比较快的做完了, 结果这个题目还不算太难, 速度是63ms (30%). 写的时候注意拿着一个有用的例子进行分析就行了, 我用的是2,4,3,2,3和5,6,4.

另外, LinkedList类的题目还有一个需要注意的小细节, 就是cache old pointer, 尤其是你的返回值的时候不要直接返回用来iterate的这个pointer, 比如我这里一开始返回的是res就不对; 这个坑好像踩过好几次了, 尽量避免, 不然真正面试的时候被这种小东西打乱心态是不划算的;

editorial

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {  
    ListNode dummyHead = new ListNode(0);  
    ListNode p = l1, q = l2, curr = dummyHead;  
    int carry = 0;  
    while (p != null || q != null) {  
        int x = (p != null) ? p.val : 0;  
        int y = (q != null) ? q.val : 0;  
        int sum = carry + x + y;  
        carry = sum / 10;  
        curr.next = new ListNode(sum % 10);  
        curr = curr.next;  
        if (p != null) p = p.next;  
        if (q != null) q = q.next;  
    }  
    if (carry > 0) {  
        curr.next = new ListNode(carry);  
    }  
    return dummyHead.next;  
}

我上面的代码实际上是一个pre leaf判断的, 这个人的是一个leaf判断的; 写的时候确实用到更多的小技巧, 比如dummyhead和循环内部的p和q的conditional advance. 总体来说值得学习;

discussion最优解, 类似的. 作者后来去Google了:

public class Solution {  
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {  
        ListNode c1 = l1;  
        ListNode c2 = l2;  
        ListNode sentinel = new ListNode(0);  
        ListNode d = sentinel;  
        int sum = 0;  
        while (c1 != null || c2 != null) {  
            sum /= 10;  
            if (c1 != null) {  
                sum += c1.val;  
                c1 = c1.next;  
            }  
            if (c2 != null) {  
                sum += c2.val;  
                c2 = c2.next;  
            }  
            d.next = new ListNode(sum % 10);  
            d = d.next;  
        }  
        if (sum / 10 == 1)  
            d.next = new ListNode(1);  
        return sentinel.next;  
    }  
}

这个解法的写法确实已经做到最简练也优雅了;

Stefan的一个写法, 更加简洁:

@StefanPochmann said in [c++] Sharing my 11-line c++ solution, can someone make it even more concise?:

How about this?

    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {  
        ListNode preHead(0), *p = &preHead;  
        int extra = 0;  
        while (l1 || l2 || extra) {  
            if (l1) extra += l1->val, l1 = l1->next;  
            if (l2) extra += l2->val, l2 = l2->next;  
            p->next = new ListNode(extra % 10);  
            extra /= 10;  
            p = p->next;  
        }  
        return preHead.next;  
    }

submission基本是波动和老答案;

Problem 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

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)  
Output: 7 -> 0 -> 8  
Explanation: 342 + 465 = 807.

Difficulty:Medium
Total Accepted:423.5K
Total Submissions:1.5M
Contributor:LeetCode
Companies
microsoftamazonbloombergairbnbadobe
Related Topics
linked listmath
Similar Questions
Multiply StringsAdd BinarySum of Two IntegersAdd StringsAdd Two Numbers II