问题

两个链表相加问题，情境类似于十进制大数加法

解决方案

原始方案

问题难点在于边界，直接上代码

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {int carryFlag = 0, plusHolder;
        ListNode res = null;
        ListNode curPos = null;
        while (true) {
            plusHolder = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carryFlag;
            carryFlag = plusHolder / 10;
            ListNode newNode = new ListNode(carryFlag == 0 ? plusHolder : (plusHolder - 10));
            if (res == null) {
                res = newNode;
                curPos = res;
            } else {
                curPos.next = newNode;
                curPos = curPos.next;
            }
            if (l1 != null)
                l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;
            if (l1 == null && l2 == null && carryFlag != 1) {
                return res;
            }
        }
    }

执行结果如下：

Runtime: 19 ms, faster than 99.90% of Java online submissions for Add Two Numbers.
Memory Usage: 48.2 MB, less than 17.15% of Java online submissions for Add Two Numbers.

从结果来看广大网友似乎更多是在节省空间复杂度上下了功夫。

改进思路，

是不是可以利用L1或者L2保存结果以节省空间呢？也就是以常见的merge链表的思路去做

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carryFlag = 0, plusHolder;
        ListNode prevPos = l1;
        ListNode headPos = l1;
        while (true) {
            plusHolder = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carryFlag;
            carryFlag = plusHolder / 10;
            if (l1 == null) {
                ListNode newNode = new ListNode(carryFlag == 0 ? plusHolder : (plusHolder - 10));
                prevPos.next = newNode;
                l1 = prevPos.next;
            } else {
                l1.val = carryFlag == 0 ? plusHolder : (plusHolder - 10);
            }
            prevPos = l1;
            l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;
            if (l1 == null && l2 == null && carryFlag != 1) {
                return headPos;
            }
        }
    }

结果在执行\空间占用上面确有优化：

Runtime: 19 ms, faster than 99.90% of Java online submissions for Add Two Numbers.
Memory Usage: 47.8 MB, less than 41.60% of Java online submissions for Add Two Numbers.