原题传送门

1. 题目描述

2. Solution 1: Iteration

1、思路
假设l1, l2均为3位数，对于阅读顺序: 百位、十位、个位，链表存储顺序: 个位、十位、百位，计算顺序与链表存储顺序一致，故遍历链表，模拟手工计算，设置进位即可。示例，见题目描述。
2、代码实现

/*
    分析:
        1. 整体的思想是模拟手算加法： p1.val(获取操作数1) + p2.val2(操作数2) = sum;
            则，保存当前位结果值为sum的个位(sum % 10)，并将sum的十位作为进位传递给下一位进行计算。
        2. 注意点1: 进入循环的条件是: p1 != null || p2 != null ,即 l1,l2只要有一个不为空就可以计算，
            避免l1, l2长度不一致，在循环外做额外的处理。
        3. 注意点2: 循环结束后，检查进位是否为0，不然需要把进位的值保存下来；
        4. 注意点3: 创建虚拟头节点dummy，是因为，每一位保存值的方式都是将值保存到的cur.next.val，而给头节点赋值则是cur.val;
            为了后续操作一致，浪费掉头节点。
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);  // 挂头结点
        int sum = 0;
        ListNode cur = dummy;
        ListNode p1 = l1, p2 = l2;
        while (p1 != null || p2 != null) {
            int n1 = p1 != null ? p1.val : 0;
            int n2 = p2 != null ? p2.val : 0;
            sum = n1 + n2 + sum;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            sum /= 10;
            if (p1 != null) p1 = p1.next;
            if (p2 != null) p2 = p2.next;
        } // end of while loop
        if (sum != 0) cur.next = new ListNode(sum);
        return dummy.next;
    }
}

time complexity: O(n)，其中n=max{l1.length, l2.length}
space complexity: O(1)

3. Solution 2: Recursion

1、思路
同迭代
2、代码实现

// Recursion
public class Solution2 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        addTwoNumbersAux(l1, l2, dummy, 0);
        return dummy.next;
    }

    private void addTwoNumbersAux(ListNode p1, ListNode p2, ListNode cur, int sum) {
        if (p1 != null || p2 != null) {
            int n1 = p1 != null ? p1.val : 0;
            int n2 = p2 != null ? p2.val : 0;
            sum = n1 + n2 + sum;
            cur.next = new ListNode(sum % 10);
            addTwoNumbersAux(p1 == null ? null : p1.next, p2 == null ? null : p2.next, cur.next, sum / 10);
        } else if (sum != 0) cur.next = new ListNode(sum);
    }
}

time complexity: O(n)，其中n=max{l1.length, l2.length}
space complexity: O(n)，递归栈

4. Follow up

What if the digits in the linked list are stored in non-reversed order? For example:
(3 -> 4 -> 2) + (4 -> 6 ->5) = 8 -> 0 -> 7

4.1 Tips 1: Stack

思路: 用栈来保存数据，首先遍历l1, l2，把结点值存储到栈中，然后逐一弹栈计算，注意设置进位，把结果也保存到栈中，最后遍历结果栈构建结果链表。
​

4.2 Tips 2

1、思路：反转链表
设函数reverse(ListNode head)是反转链表函数的定义，整体的思路

rev1 = reverse(l1);	
rev2 = reverse(l2);
r = addTwoNumbers(rev1, rev2);
res = reverse(r);

4.2.1 反转链表——迭代实现

1、思路
a) 初始态

对应操作

ListNode pre = null, p = head, r = p.next;
p.next = null;

b) 反转操作

对应操作

pre = p;
p = r;
r = r.next;
p.next = pre;

可以看到，r是下一个待处理的结点，所以退出迭代循环的条件是r为空。
2、完整代码

    public ListNode reverseList(ListNode head) {
        // corner case
        if (head == null || head.next == null) return head;
        // 初始态
        ListNode pre, p = head, r = p.next;  
        p.next = null;
        // 迭代操作
        while (r != null) {
            pre = p;
            p = r;
            r = r.next;
            p.next = pre;
        }
        return p;
    }

4.2.2 反转链表——递归实现

思路同迭代

    public ListNode reverseList(ListNode head) {
        return reverseListAux(head, null);
    }

    private ListNode reverseListAux(ListNode p, ListNode pre) {
        if (p == null) return pre;
        ListNode r = p.next;
        p.next = pre;
        return reverseListAux(r, p);
    }