题目

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
Explanation: 342 + 465 = 807.

预先定义好的节点类：

/**
 * Definition for singly-linked list.
 */
  public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }

思路：初等数学即可

由于存储结构是逆序，在很大程度上方便了程序的设计。只需要按照竖式计算的相关规则进行编程即可。在空间上，可以使用一个额外的变量来保存进位信息。

链表运算示意图

需要考虑的一些特别情况

测试用例	说明
l1=[0,1] ; l2=[0,1,2]	当一个列表比另一个列表长时。
l1=[] ; l2=[0,1]	当一个列表为空时，即出现空列表。
l1=[9,9] ;l2=[1]	求和运算最后可能出现额外的进位，这一点很容易被遗忘

java代码

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;
}

复杂度分析

1. 时间复杂度：O(max(m,n))
2. 空间复杂度：O(max(m,n))

值得关注的一些地方

1.使用取余的方式进行节点值的计算。
2.使用计算机除法运算进行进位carry的计算。（不使用boolean标志位是因为标志位还需要判断，使用carry值的话，可以直接参与计算）

上述java代码的可以改进的一些地方

1. 上述代码做了多余的操作，实际上，当两个链表不一样长的时候，一条链表超出另外一条链表的部分可以不进行相关计算，直接链接到链表上就行。也就是上述的实现代码存在多余操作。

改进后的java代码

    private static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode result = l1;
        int carry = 0;
        int sum = 0;
        while (true) {
            sum = l1.val + l2.val + carry;
            carry = sum / 10;
            l1.val = sum % 10;
            if (l1.next == null && l2.next == null) {
                if (carry > 0) {
                    l1.next = new ListNode(carry);
                }
                return result;
            } else if (l1.next == null ) {
                if (carry > 0) {
                    l1.next = new ListNode(1);
                    carry = 0;
                    l1 = l1.next;
                    l2 = l2.next;
                } else {
                    l1.next = l2.next;
                    return result;
                }
            } else if (l2.next == null) {
                if (carry > 0) {
                    l2.next = new ListNode(1);
                    carry = 0;
                    l1 = l1.next;
                    l2 = l2.next;
                } else {
                    return result;
                }
            } else {
                l1 = l1.next;
                l2 = l2.next;
            }
        }
    }

改进后的复杂度分析

1. 时间复杂度：O(min(m,n))。需要注意到的是，如果遇到极端情况，也就是类似于1+9999999这样的情况。就不能使用min进行分析了
2. 空间复杂度：近似于O(1)。这里需要注意，也是如果出现极端情况，类似于1+9999999.那么就需要额外创建新的节点。