2. 两数相加

题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

思路

本质上就是竖式相加，可以通过模拟的方式去做，为了保存结果，我们可以创建一个 head 头，接下来遍历 l1 和 l2，如果非空就求和，然后对和进行处理，申请一个新的节点，最后返回 head.next 即可。

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        head = ListNode()
        c1, c2 = l1, l2
        s = 0
        curr = head
        while c1 or c2 or s:
            if c1:
                s += c1.val
                c1 = c1.next
            if c2:
                s += c2.val
                c2 = c2.next
            curr.next = ListNode(s%10)
            curr = curr.next
            s //= 10
        return head.next

时间复杂度为 $O(n)$，为遍历两个链表的时间。