美文网首页LeetCode刷题
[LeetCode]2-两数相加

[LeetCode]2-两数相加

作者: 杏仁小核桃 | 来源:发表于2018-11-05 18:51 被阅读3次

    2. 两数相加
    给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
    你可以假设除了数字 0 之外,这两个数字都不会以零开头。
    示例:
    输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出:7 -> 0 -> 8
    原因:342 + 465 = 807

    解法1:

    常规思路, 关键点: 头结点, 进位, 链表长度不一致时

    class Solution:
        def addTwoNumbers(self, l1, l2):
            carry = 0  #进位值
            isFirst = True  #头结点flag
            currentNode = None  #当前结点
            head = None  #头结点
            while (l1 or l2 or carry != 0): #循环条件: l1, l2的遍历没结束, 或有高位进位时
                val1 = 0
                val2 = 0
                if l1:
                    val1 = l1.val
                    l1 = l1.next
                if l2:
                    val2 = l2.val
                    l2 = l2.next
                unit = val1 + val2 + carry
                if unit >= 10:
                    carry = 1
                    unit = unit%10
                else:
                    carry = 0
                
                node =  ListNode(unit)
                if isFirst:
                    currentNode = node
                    head = currentNode
                    isFirst = False
                else:
                    currentNode.next = node
                    currentNode = currentNode.next
            return head
    

    解法2

    给定一个空的头结点, 简化代码.

    class Solution:
        def addTwoNumbers(self, l1, l2):
            head = ListNode(0)  #头结点设为空结点
            current = head
            carry = 0
            while (l1 or l2 or carry !=0):
                if l1:
                    carry += l1.val
                    l1 = l1.next
                if l2:
                    carry += l2.val
                    l2 = l2.next
                node = ListNode(carry%10)
                carry = carry//10
                current.next = node
                current = current.next
    
            return head.next
    

    相关文章

      网友评论

        本文标题:[LeetCode]2-两数相加

        本文链接:https://www.haomeiwen.com/subject/zaxexqtx.html