LeetCode 2 两数相加

题目

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解题思路

1. 创建一个虚拟头节点，用于两个链表相加完之后的遍历
2. 先考虑两个链表中的元素都不为空的情况：
   • 两个元素相加的值为 node = node1 + node2 + carry, 其中carry是上一个节点相加之后的进位，大于10进位，小于10，不进位。
   • 当前的节点： node % 10
   • 考虑对下一个节点的影响：carry = node // 10
3. 当只存在一个链表时，与上面唯一的不同就是node中没有node1或node2
4. 最后不要忘记要考虑最后一位carry是否存在，存在+1

代码

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next =None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        li = ListNode(0) # 虚拟头节点
        cur_li= li
        carry = 0
        while l1 and l2:
            node = l1.val + l2.val + carry
            cur_li.next = ListNode(node%10)
            carry = node // 10
            cur_li, l1, l2 = cur_li.next, l1.next, l2.next
        l2 = l2 if l2 else l1
        while l2:
            node = l2.val + carry
            cur_li.next = ListNode(node%10)
            carry = node // 10
            cur_li, l2 = cur_li.next, l2.next
        if carry:
            cur_li.next = ListNode(1)
        return li.next