LeetCode 2 Add Two Numbers

一、题目链接

https://leetcode.com/problems/add-two-numbers/

二、解答

这道题基本上只有一个解答，即每个节点顺次加过去，然后需要处理的就是进位，加一个变量 carry 即可。

代码

# -*- coding: utf-8 -*-
# @File  : leet_02.py
# @Author: FanyFull
# @Date  : 2021/7/9

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

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        res = ListNode()
        tmp = res
        carry = 0
        while l1 != None and l2 != None:
            tmp.next = ListNode()
            tmp = tmp.next
            tmp.val = (l1.val + l2.val + carry) % 10
            carry = (l1.val + l2.val + carry) // 10
            l1 = l1.next
            l2 = l2.next
        l3 = l1 if l1 != None else l2
        while l3 != None:
            tmp.next = ListNode()
            tmp = tmp.next
            tmp.val = (l3.val + carry) % 10
            carry = (l3.val + carry) // 10
            l3 = l3.next
        if carry != 0:
            tmp.next = ListNode()
            tmp = tmp.next
            tmp.val = carry
        return res.next

class Solution2:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy_head = ListNode()
        # 用 p 和 q 以将 l1 和 l2 保护起来
        p = l1
        q = l2
        curr = dummy_head
        carry = 0
        while p != None or q != None:
            x = p.val if p != None else 0
            y = q.val if q != None else 0
            sum = carry + x + y
            carry = sum // 10
            curr.next = ListNode(sum % 10, None)
            curr = curr.next
            if p != None:
                p = p.next
            if q != None:
                q = q.next
        if carry > 0:
            curr.next = ListNode(carry, None)
        return dummy_head.next

if __name__ == '__main__':
    # solution = Solution()
    solution = Solution2()
    l1 = ListNode(2, ListNode(4, ListNode(3, None)))
    l2 = ListNode(5, ListNode(6, ListNode(4, None)))
    res = solution.addTwoNumbers(l1, l2)
    while res != None:
        print(res.val, end=' ')
        res = res.next
    print('\n-------')
    l1 = ListNode(0, None)
    l2 = ListNode(0, None)
    res = solution.addTwoNumbers(l1, l2)
    while res != None:
        print(res.val, end=' ')
        res = res.next
    print('\n------')
    l1 = ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9 ,None)))))))
    l2 = ListNode(9, ListNode(9, ListNode(9, ListNode(9, None))))
    res = solution.addTwoNumbers(l1, l2)
    while res != None:
        print(res.val, end=' ')
        res = res.next

说明一下，这里的 Solution1 和 Solution2 的思想是一样的，第一个解法是我手撸的，第二个是根据官方 Java 解答改写的，相比之下，第二个要优雅一点。

时间复杂度：$O(max(m, n))$，m、n 分别是 $l_1$ 和 $l_2$ 的长度。 空间复杂度：$O(max(m, n))$。