Leetcode第二题：两数相加

77 阅读 0 评论 51 点赞

我是靠谱客的博主飞快豌豆，这篇文章主要介绍Leetcode第二题：两数相加，现在分享给大家，希望可以做个参考。

题目：

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

个人思路：

两链表同时遍历，有进位就为下一个进位的值+1。注意特殊情况！

官方答案推荐：

同上。若不是逆序，则可用栈，依旧要从最小位开始计算。

python代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 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:
        curNode = ListNode(0)
        l3 = curNode
        carry = 0
        while l1 or l2:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            curVal = val1 + val2 + carry
            if(curVal>=10):
                curVal = curVal % 10
                carry = 1
            else:
                carry = 0
            
            curNode.next = ListNode(curVal)
            curNode = curNode.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        if(carry>0):
            curNode.next = ListNode(1)
        return l3.next