前言

这个题目稍显简单，但是也可以作为练习翻转链表和头插法的基础。除此之外，发现三目运算符深受CPU喜爱，但同时也存在全部运算导致改变的缺点。

一、两数相加

二、翻转链表+头插

package everyday;

// 两数相加。
public class AddTwoNumbers {
    /*
    target:两个用链表代表的数相加。
    类似与大数（数组形式）之和，但数组形式可以随机读取，读前读后，但单向链表就只能从链头开始读。
    所以考察知识点为：
    1-链表翻转：for | 递归都可
    2-大数相加
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 翻转链表,for | recursion。这个题好像不用先翻转，太拉跨了。
        // l1 = reverseListForV1(l1);
        // l2 = reverseListRecursionV2(l2);
        // 大数相加。dummyHead + 头插翻转 + 又翻转回来，    纯属练习头插法。
        return reverseListForV1(twoListAdd(l1, l2));
    }

    /**
     * 1-两数链表相加,2-返回头节点。
     *
     * @param l1 一个链表。
     * @param l2 另一个被加的链表。
     * @return 相加之后的新链表头节点。
     */
    private ListNode twoListAdd(ListNode l1, ListNode l2) {
        int plus = 0;// 进位多少。
        ListNode dummyHead = new ListNode();// 统一头与非头节点的操作差异。

        // 两者对应相加
        while (l1 != null && l2 != null) {
            int val = l1.val + l2.val + plus;
            // 采用头插法，防止再次翻转。
            ListNode next = dummyHead.next;
            ListNode node = new ListNode(val % 10);
            dummyHead.next = node;
            node.next = next;
            // 更新进位数。
            plus = val / 10;
            // 更新下一个相加节点，保持循环。
            l1 = l1.next;
            l2 = l2.next;
        }
        // 谁不为空，把剩下的和plus一起运算。
        // bug1:三目运算是会把分支都运算了，不像if那么选择，所以才更得CPU的喜爱。
        // plus = l1 != null ? singleListAdd(dummyHead, l1, plus) : singleListAdd(dummyHead, l2, plus);
        if (l1 != null) plus = singleListAdd(dummyHead, l1, plus);
        if (l2 != null) plus = singleListAdd(dummyHead, l2, plus);
        // 如果最终的plus不为0，给plus也生成一个节点。
        // 同bug1:三目运算是会把分支都运算了，不像if那么选择，所以才更得CPU的喜爱。
        // return 0 != plus ? (dummyHead.next = new ListNode(plus)).next : dummyHead.next;
        if (0 != plus) {
            ListNode next = dummyHead.next, node = new ListNode(plus);
            dummyHead.next = node;
            node.next = next;
        }
        // 返回最终的头节点。
        return dummyHead.next;
    }

    /**
     * 当个链表和进位数进行相机，返回最后的进位数。
     *
     * @param dummy
     * @param l
     * @param plus
     * @return
     */
    private int singleListAdd(ListNode dummy, ListNode l, int plus) {
        while (l != null) {
            int val = l.val + plus;
            // 头插。
            ListNode next = dummy.next;
            ListNode node = new ListNode(val % 10);
            dummy.next = node;
            node.next = next;

            // 更新plus.
            plus = val / 10;
            // 更新下一个操作节点，保持循环。
            l = l.next;
        }
        // 返回最后的进位数。
        return plus;
    }

    /**
     * 1-翻转链表，2-并返回新的头节点。
     *
     * @param l 需要翻转的链表。
     * @return 翻转之后的新头节点。
     */
    private ListNode reverseListRecursionV2(ListNode l) {
        // 当l本身就是null时，结束调用。
        if (l == null) return null;
        // 当递归到最后一个时，这条链表路径走完了，开始回溯进行修改next。
        if (l.next == null) return l;
        // 利用函数栈记录这条有序路径。
        ListNode head = reverseListRecursionV2(l.next);
        // 修改next.
        l.next.next = l;
        l.next = null; // 只为防止第一个节点不会被覆盖，所以赋值为null。
        // 一如既往的返回头节点。
        return head;
    }

    /**
     * 1-翻转链表，2-并返回新的头指针。（for 循环版）
     *
     * @param l 需要被翻转的链表。
     * @return 新的头指针。
     */
    private ListNode reverseListForV1(ListNode l) {
        ListNode pre = null;
        while (l != null) {
            // 记录下一个要修改的节点，保证断链时，还能拿到它。
            ListNode next = l.next;
            // 改变当前节点next指向，指到前一个节点。
            l.next = pre;
            // 更新pre = l;更新l = next,保证继续循环。
            pre = l;
            l = next;
        }
        // 最后遍历到null才结束，所以返回null的前向节点即可。
        return pre;
    }


    // Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

总结

1）翻转链表+头插。
2）三目运算符。

参考文献

[1] LeetCode 两数相加