AddTwoNumbers

/*
    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
    */

此题不能用暴力法，即将 List1 和 List2 都转化为数，然后相加，然而笔者实现了这一暴力算法过程：

• 利用 10 的乘方来恢复 List 所表示的数，再将两个数相加，将和作为字符串处理，将字符串中每一个字符所代表的数字插入到一个空链表头引领的 List 中，最后返回空链表头的下一个节点

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int l1Num = 0;
        int num1 = 0;
        int l2Num = 0;
        int num2 = 0;
        while(l1 != null) {
            l1Num = l1Num + l1.val * (int)Math.pow(10, num1);
            l1 = l1.next;
            num1++;
        }
        while(l2 != null) {
            l2Num = l2Num + l2.val * (int)Math.pow(10, num2);
            l2 = l2.next;
            num2++;
        }
        int sum = l1Num + l2Num;
//        System.out.println(l1Num + " " + l2Num);
        String sumString = sum + "";
        System.out.println(sumString);
        ListNode emptyHead = new ListNode(0);
        ListNode curr = emptyHead;
        for(int i = sumString.length() - 1; i >= 0; i--) {
            ListNode Num = new ListNode(Integer.valueOf(sumString.charAt(i) + ""));
            curr.next = Num;
            curr = curr.next;
        }
        return emptyHead.next;
    }

这样虽然能够满足题目中给出的例子：（结果是 807 对应的 7 -> 0 -> 8）

public static void main(String[] args) {

        ListNode l11 = new ListNode(2);
        ListNode l12 = new ListNode(4);
        ListNode l13 = new ListNode(3);
        l11.next = l12;
        l12.next = l13;

        ListNode l21 = new ListNode(5);
        ListNode l22 = new ListNode(6);
        ListNode l23 = new ListNode(4);
        l21.next = l22;
        l22.next = l23;

        ListNode head = addTwoNumbers(l11,l21);

        while(head != null) {
            System.out.print(head.val);
            head = head.next;
        }
    }

但是它存在一个致命的 Overflow 问题，即处理 long 类型整数时，会出现溢出：

public static void main(String[] args) {

        ListNode l11 = new ListNode(9);

        ListNode l21 = new ListNode(1);
        ListNode l22 = new ListNode(9);
        ListNode l23 = new ListNode(9);
        ListNode l24 = new ListNode(9);
        ListNode l25 = new ListNode(9);
        ListNode l26 = new ListNode(9);
        ListNode l27 = new ListNode(9);
        ListNode l28 = new ListNode(9);
        ListNode l29 = new ListNode(9);
        ListNode l210 = new ListNode(9);

        l21.next = l22;
        l22.next = l23;
        l23.next = l24;
        l24.next = l25;
        l25.next = l26;
        l26.next = l27;
        l27.next = l28;
        l28.next = l29;
        l29.next = l210;

        ListNode head = addTwoNumbers(l11,l21);

        while(head != null) {
            System.out.print(head.val);
            head = head.next;
        }
    }

• 其结果并不是 10000000000，而是 8045600141
  故在提交时也不能通过
  弃之，改用他法

public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        // 与上法相同，创建空链表头，用来生成新链表返回空链表头下一个节点
        ListNode emptyHead = new ListNode(0);
        ListNode curr = emptyHead;
        ListNode p = l1;
        ListNode q = l2;
        // carry 是进位符，如果两个节点中的数字相加导致向下一位进位，则将 carry 置成 1，不进位 carry 为 0，所以后续 carry 参与节点中数字的相加
        int carry = 0;
        while(p != null || q != null) {
            int x;
            int y;
            if(p == null) {
                x = 0;
            }
            else {
                x = p.val;
            }
            if(q == null) {
                y = 0;
            }
            else {
                y = q.val;
            }
            // 得到总和为表一节点数字加表二节点数字加进位符
            int sum = x + y + carry;
            // 该节点的新数字为综合除以 10 之后的余数
            int newCurrNumber = (sum) % 10;
            ListNode newNumber = new ListNode(newCurrNumber);
            // 连接上之前的链表
            curr.next = newNumber;
            curr = curr.next;
            // 如果和大于等于 10，进位符为 1，下一位（节点）的两个数进行计算时要加进位符 1，否则不进位（进位符为 0）
            if(sum >= 10) {
                carry = 1;
            }
            else {
                carry = 0;
            }
            // l1 和 l2 向后遍历 
            if(p != null) {
                p = p.next;
            }
            if(q != null) {
                q = q.next;
            }
        }
        // 如果最后一次运算过后，进位符仍然为 1，则说明产生了新的位，为表示新数字的链表创建一个新的节点
        if(carry == 1) {
            curr.next = new ListNode(carry);
        }
        // 返回空链表头的下一个节点
        return emptyHead.next;
    }

这样就通过了测试