题目出处

来自于leetcode

题目描述

You are given two linked lists representing two non-negative numbers. 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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

解读

给定两个表示两个非负整数的单链表，这两个数按反序保存在单链表中，把两个数相加并返回一个单链表。
给定的例子为342 + 465 = 807

第一版答案

1. 从两个单链表的开头相加，记住进位；
2. 几个边界条件需要注意：

• 入参的两个单链表有可能为空，若一个为空，则直接返回另一个即可；
• 两个单链表长度可能不一样，在相加结束后需要把比较长的剩余的数值拷贝过去；
• 进位也需要考虑，如5 + 5 = 10， 当两个单链表处理完毕后，如果还有进位，还需要增加一个节点

代码如下

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1:
            return l2
        if not l2:
            return l1
           
        carry = 0
        sums = l1.val + l2.val + carry
        carry = sums / 10
        res = ListNode(sums % 10)
        l1 = l1.next
        l2 = l2.next
       
        node  = res
        while l1 and l2:
            sums = l1.val + l2.val + carry
            tmp = ListNode(sums % 10)
            carry = sums / 10
           
            node.next = tmp
            node = node.next
            l1 = l1.next
            l2 = l2.next
           
        while l1:
            sums = l1.val + carry
            tmp = ListNode(sums % 10)
            carry = sums / 10
           
            node.next = tmp
            node = node.next
            l1 = l1.next
           
        while l2:
            sums = l2.val + carry
            tmp = ListNode(sums % 10)
            carry = sums / 10
           
            node.next = tmp
            node = node.next
            l2 = l2.next
       
        while carry:
            tmp = ListNode(carry % 10)
            carry = carry / 10
           
            node.next = tmp
            node = node.next
           
        return res

第二版答案

第一版答案中的代码不够精炼，从以下两个地方入手：

1. 入参判断，对l1和l2的检查上，先定义一个头节点，返回头节点的next，这样可以避免处理l1或l2为空的情形，将链表中所有的节点一视同仁进行处理；
2. 将四个while语句合并处理

代码如下：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        head = ListNode(0)
           
        carry = 0
        node  = head
        while l1 or l2 or carry:
            val1, val2 = 0, 0
            if l1:
                val1 = l1.val
                l1 = l1.next
           
            if l2:
                val2 = l2.val
                l2 = l2.next
               
            sums = val1 + val2 + carry
            tmp = ListNode(sums % 10)
            carry = sums / 10
           
            node.next = tmp
            node = node.next
           
        return head.next

代码简洁了许多，由于增加了比较多的比较，效率会稍微下降点。