乐趣区

两数相加Python3

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

解题思路:设置两个指针指向两条链表,构造新节点存储两个当前指针节点的值,当前节点被遍历过后,指针后移。对于满 10 进 1 的情况,设置一个变量判断即可。

代码如下 (~▽~):

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

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1==None:
            return l2
        elif l2==None:
            return l1
        else:
            h1 = l1
            h2 = l2
            flag = 0
            new = ListNode(0)
            res = new
            while h1 or h2:
                temp = 0
                if h1:
                    temp += h1.val
                    h1 = h1.next
                if h2:
                    temp += h2.val
                    h2 = h2.next
                if flag == 1:
                    temp += 1
                    flag = 0
                if temp >= 10:
                    temp -= 10
                    flag = 1
                res.next = ListNode(temp)
                res = res.next
            if flag == 1:
                res.next = ListNode(1)   
            return new.next

时间与空间复杂度:

题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…

退出移动版