Skip to main content

Add Two Numbers

Add Two Numbers

描述

给定两个链表, 输出两个链表的和

示例:
输入: (2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: (7 -> 0 -> 8)

分析

这道题并没有什么特别的地方, 遍历相加输出就好了, 需要注意的是处理链表长度不一样等边界情况, 最终如果有进位, 记得加一个元素

答案

遍历, 复杂度为\(O(m+n)\)

# 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 l1 is None:
            return l2
        if l2 is None:
            return l1

        res = ListNode(None)
        root = res
        u = 0
        while True:
            if l1 is None and l2 is None:
                break
            if l1 is None:
                p1 = 0
            else:
                p1 = l1.val

            if l2 is None:
                p2 = 0
            else:
                p2 = l2.val

            s = p1 + p2 + u
            if s < 10:
                u = 0
                res.val = s
            else:
                res.val = s - 10
                u = 1
            if l1 is not None:
                l1 = l1.next
            if l2 is not None:
                l2 = l2.next
            if l1 is not None or l2 is not None:
                res.next = ListNode(None)
                res = res.next
        if u == 1:
            res.next = ListNode(1)
        return root
打赏
微信扫一扫支付
微信logo微信扫一扫, 打赏作者吧~