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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

思路

这道题不需要非常复杂的思考，但是需要判断多个边界条件。尤其是加到最后，只剩一个链表可以操作，应该如何处理。可以看看后面参考资料给出的代码，简洁明了，不知道比我高到哪儿去了。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0);
        ListNode cur = root;
        int carry = 0;
        ListNode remain = null;
        while(true){
            int tmp = 0;
          	//需要注意前一个数的进位
            if(remain == null) tmp = l1.val + l2.val + carry;
            else tmp = remain.val + carry;
            if(tmp >= 10){
                tmp -= 10;
                carry = 1;
            }
            else carry = 0;
            cur.val = tmp;
            ListNode next_node = new ListNode(0);
          	//如果被加数和加数都存在，直接将两个链表的数相加
            if(remain == null){
                if(l1.next != null && l2.next != null){
                    l1 = l1.next;
                    l2 = l2.next;
                    cur.next = next_node;
                    cur = cur.next;
                }
              	//走到了某一个链表的尾部
                else{
                    if(l1.next == null && l2.next == null) break;
                    else if(l1.next == null && l2.next != null) {
                        remain = l2.next;
                        cur.next = next_node;
                        cur = cur.next;
                    }
                    else if(l1.next != null && l2.next == null) {
                        remain = l1.next;
                        cur.next = next_node;
                        cur = cur.next;
                    }
                }
            }
            //把链表的剩下部分加上
            else{
                if(remain.next != null) {
                    remain = remain.next;
                    cur.next = next_node;
                    cur = cur.next;
                }
                else break;
            }
        }
        //加到最后仍然有进位，把这个数给加上
        if(carry == 1){
            ListNode next_node = new ListNode(1);
            cur.next = next_node;
            cur = cur.next;
        }
        
        return root;
    }
}

参考资料：https://discuss.leetcode.com/topic/39130/4ms-11lines-java-solution