题目

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例：

1
2
3

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

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

1
2
3

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解题方法

链表操作

最初的想法是分三步：第一，判断两个数是否存在0，则直接返回另一个链表；第二，保存结果的头结点，判断链表长度和初始化进位标志，对两个数的前相同的位进行计算，并调整进位标志状态；第三，处理位数较高的那个数剩下的几位。

实现代码如下，最终跑了49ms，这段代码实在是太冗长而且难看了，所以强迫症必须要对其优化，大佬们避免辣眼睛可以直接看第二段代码。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // if there exit 0
        if (l1.val == 0 && l1.next == null)
            return l2;
        else if (l2.val == 0 && l2.next == null)
            return l1;

        // both l1 & l2 are not zero
        ListNode result = new ListNode(0);
        // store the headnode
        ListNode rootNode = result;
        boolean carry = false;
        int tmp;
        while (l1 != null && l2 != null) {
            result.next = new ListNode(0);
            result = result.next;
            if (carry) {
                tmp = l1.val + l2.val + 1;
                if (tmp >= 10) {
                    result.val = tmp % 10;
                }else{
                    carry = false;
                    result.val = tmp;
                }
            } else {
                tmp = l1.val + l2.val;
                if (tmp >= 10) {
                    carry = true;
                    result.val = tmp % 10;
                }else{
                    result.val = tmp;
                }
            }
            l1 = l1.next;
            l2 = l2.next;
        }

        // handle the rest of the biger number
        while(l1 != null){
            result.next = new ListNode(0);
            result = result.next;
            if (carry) {
                tmp = l1.val + 1;
                if (tmp >= 10){
                    result.val = tmp % 10;
                }else{
                    result.val = tmp;
                    carry = false;
                }
            }else{
                result.val = l1.val;
            }
            l1 = l1.next;
        }
        while(l2 != null){
            result.next = new ListNode(0);
            result = result.next;
            if (carry) {
                tmp = l2.val + 1;
                if (tmp >= 10){
                    result.val = tmp % 10;
                }else{
                    result.val = tmp;
                    carry = false;
                }
            }else
                result.val = l2.val;
            l2 = l2.next;
        }
        
        // at last jugde whether carry is 1
        if (carry){
            result.next = new ListNode(0);
            result.next.val = 1;
        }
		
        // return headnode 
        result = rootNode.next;

        return result;
    }
}

简化代码

可以看到上面的代码冗余且难看，对上面代码的循环判断部分进行简化，结果反而跑了66ms。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode current = new ListNode(0);
        ListNode root = current;
        int carry = 0;
        while (l1 != null || l2 != null || carry == 1) {
            current.next = new ListNode(0);
            current = current.next;
            current.val = (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0) + carry;
            carry = current.val / 10;
            current.val = current.val % 10;
            l1 = l1 != null ? l1.next : null;
            l2 = l2 != null ? l2.next : null;
        }
        return root.next;
    }
}

再次优化

代码进行了大量简化后发现速度反而降下来了，仔细查看循环部分while (l1 != null || l2 != null || carry == 1) ，其实不用每次都对进位标志carry进行判断，只需要在最后计算完之后再次判断是否进位，来确定最后是否要增加一个节点。代码优化如下，这段代码跑了38ms，超过leetcode前86.77%的java提交，但是看了看第一的代码，其实跟我这个是一样的，可能是我提交的时候在刷题的人比较多吧。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode current = new ListNode(0);
        ListNode root = current;
        int carry = 0;
        int tmp;

        while (l1 != null || l2 != null) {
            tmp = (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0) + carry;
            carry = tmp / 10;
            tmp = tmp % 10;
            current.next = new ListNode(tmp);
            current = current.next;
            l1 = l1 != null ? l1.next : null;
            l2 = l2 != null ? l2.next : null;
        }

        if (carry == 1){
            current.next = new ListNode(1);
        }

        return root.next;
    }
}

结语

编程也是一门艺术，对代码精益求精的过程，就像古代大师制作雕刻品一样，经过各种细节的打磨，才能雕刻出卓越的作品。

这是笔者刷leetcode的开始，代码都托管在我的Github上，有兴趣的朋友可以相互交流，请多多指教。