链表求和12 · Add Two Numbers

反向存储，从左往右加

［抄题］：

你有两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形式返回和。给出两个链表 3->1->5->null 和 5->9->2->null，返回 8->0->8->null

[暴力解法]：

时间分析：

空间分析：

［思维问题］：

直接从左往右加就行，没看出来。
链表结构改变时要添加dummy，返回的是dummy.next 忘了。

［一句话思路］：

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

代码前后检查：null的前一位仍要继续走到null，有null时sum+0
此处的carry不用求和，依据题目要求变成新的节点

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

注意流程：求和、取整数、取余数、加carry

［复杂度］：Time complexity: O(n) Space complexity: O(1)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

445. Add Two Numbers II反过来：用stack

[代码风格] ：

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    /*

     * @param l1: the first list

     * @param l2: the second list

     * @return: the sum list of l1 and l2

     */

    public ListNode addLists(ListNode l1, ListNode l2) {

        //intialize

        ListNode dummy = new ListNode(0);

        ListNode tail = dummy;//

        //sum

        int carry = 0;

        for (ListNode i = l1, j = l2; i != null || j != null;) {

            int sum = carry;

            sum += (i != null)? i.val: 0;

            sum += (j != null)? j.val: 0;

            // %

            tail.next = new ListNode(sum % 10);

            tail = tail.next;

            // /

            carry = sum / 10;

            i = (i == null)? i : i.next;//i, j should go down

            j = (j == null)? j : j.next;//judge itself

        }

        //carry

        if (carry != 0) {

            tail.next = new ListNode(carry);

        }//turn carry into a node

        return dummy.next;//forget

    }

}

正向存储，从右往左加