Add Two Numbers

因为整个链表是反过来的，使得逻辑方面实现不会那么困难，因为两个链表的每一位都是一一对位不会错位的，所以我们只需要先把两个数字的共有位计算完成之后再单独计算更长的那个数字即可，其实这道题更应该思考的是正向排列的两个列表应该如何计算，个人现在觉得最好的思路还是把两个链表反转过来之后再用这里的算法就好，下面是代码，个人觉得逻辑清晰且整洁，可以背下来了

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = ListNode('dumm')
        cur = dummy

        step = 0
        l, r = l1, l2
        while l and r:
            step, val = divmod(l.val + r.val + step, 10)
            cur.next = ListNode(val)
            cur = cur.next
            l = l.next
            r = r.next

        while l:
            step, val = divmod(l.val + step, 10)
            cur.next = ListNode(val)
            cur = cur.next
            l = l.next

        while r:
            step, val = divmod(r.val + step, 10)
            cur.next = ListNode(val)
            cur = cur.next
            r = r.next 

        if step:
            cur.next = ListNode(1)
        return dummy.next

Java版本

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(-1);
        ListNode cur = result;

        int step = 0;
        while (l1 != null && l2 != null) {
            int val = l1.val + l2.val + step;
            cur.next = new ListNode(val % 10);
            cur = cur.next;
            l1 = l1.next;
            l2 = l2.next;
            step = val / 10;
        }

        while (l1 != null) {
            int val = l1.val + step;
            cur.next = new ListNode(val % 10);
            cur = cur.next;
            l1 = l1.next;
            step = val / 10;
        }

        while (l2 != null) {
            int val = l2.val + step;
            cur.next = new ListNode(val % 10);
            cur = cur.next;
            l2 = l2.next;
            step = val / 10;
        }

        if (step != 0) {
            cur.next = new ListNode(step);
        }

        return result.next;
    }    
}

Add Two Numbers II

要求我们不反转链表，不改变输入的链表，那只能先把两个数加起来然后再倒序垒一个结果出来了，这里唯一需要注意的是0，0链表，非常讨厌

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 and not l2:
            return None

        left, right = 0, 0
        while l1 or l2:
            if l1:
                left = 10 * left + l1.val
                l1 = l1.next
            if l2:
                right = 10 * right + l2.val
                l2 = l2.next

        left += right
        dummy = ListNode('d')
        pre = dummy
        while left:
            tmp = pre.next
            left, digit = divmod(left, 10)
            pre.next = ListNode(digit)
            pre.next.next = tmp
        return dummy.next if dummy.next else ListNode(0)