提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

​LeetCode刷题实战445：两数相加 II

算法 计算
2023-03-15 23:24:27 时间

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 两数相加 II，我们先来看题面：

https://leetcode-cn.com/problems/add-two-numbers-ii/

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

示例

解题

https://blog.csdn.net/u013243296/article/details/116455362

题目给出的链表所表示的数字，从左到右是高位到低位，做加法需要从低位到高位开始相加进位来计算，所以想到使用两个栈来存储链表表示的节点的值。再考虑进位的关系，将两个链表从右向左开始计算节点表示的值，对10进行整除计算商和余数，商就是进位的值，余数就是要新建的链表的节点的值，新建的链表是从低位开始建立，因为先计算的低位的值的节点，所以初始化一个空节点ans，ans的指向经过计算，从低位到高位，最后指向的就是最高位，同时也是头结点，返回即可。具体实现看代码及注释。

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 定义两个栈用于存储链表中的节点值
        stack1, stack2 = [], []
        # 最后的结果链表
        ans = None
        # 进位
        carry = 0

        while l1:
            stack1.append(l1.val)
            l1 = l1.next
        
        while l2:
            stack2.append(l2.val)
            l2 = l2.next

        while stack1 or stack2 or carry != 0:
            a = 0 if not stack1 else stack1.pop()
            b = 0 if not stack2 else stack2.pop()

            num = a + b + carry
            
            # res是余数，就是要生成的新节点的值
            carry, res = divmod(num, 10)

            # cur_node是从低位到高位来建立新的节点，根据是出栈的值是低位先出栈来计算
            cur_node = ListNode(res)
            cur_node.next = ans
            # ans左移
            ans = cur_node 
        
        return ans

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。

相关文章