Leedcode 链表两数相加 Python包含反思过程

简介: Leedcode 链表两数相加 Python包含反思过程

问题描述:

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

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


image.png

# 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:
        def get_number(node):
            res,count=node,0
            while node:
                count+=1
                node=node.next
            number=0
            for i in range(0,count):
                number+=res.val*10**i
                res=res.next
            return number
        answer=int(str(get_number(l1)))+int(str(get_number(l2)))
        res=ListNode()
        c=res
        for j in str(answer)[::-1]:
            c.next=ListNode(int(j))
            c=c.next
        c.next=None
        return res.next        

f788abca758d432890e513f3fce78820.png

基本的思路就是分开处理两个链表得到他们的对应十逆序进制数字,两数相加再创建链表逆序输出 一共逆序了两次 其实就是暴力运算

emm算法还是得优化

借鉴上一篇博客的思路两数之和双指针板子 通过双指针解决~

# 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:
        add=0
        res=answer=ListNode(-1)
        def count(node):
            s=0
            while node:
                s+=1
                node=node.next
            return s
        i,j=count(l1),count(l2)
        while i>0 or j>0:
            x=l1.val if i>0 else 0
            y=l2.val if j>0 else 0
            sum=x+y+add
            add=sum//10
            answer.next=ListNode(sum%10)
            l1=l1.next if i>0 else l1
            l2=l2.next if j>0 else l2
            answer=answer.next
            i,j=i-1,j-1
        if add>0:answer.next=ListNode
        return res.next

其实两个有些近似,可以归纳到一个专题来,加法专题~

9a501fc0dd654a1697302516e70883c6.png


你以为这就结束了吗?不,上面优化后的算法只是基于以往的模板优化虽然速度有很大提升,但依旧有很多地方可以改进

终极版:


# 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:
        add=0
        res=answer=ListNode(-1)
        while l1 or l2:#只要还有没有遍历的数字
            x=l1.val if l1 else 0 #只要不是末节点(末节点是None 逻辑表现False)
            y=l2.val if l2 else 0
            sum=x+y+add
            add=sum//10
            answer.next=ListNode(sum%10)
            if l1:l1=l1.next#只要不是末节点 跳到下一个节点 否则就停在末节点
            if l2:l2=l2.next
            answer=answer.next
        if add>0:answer.next=ListNode(add)
        return res.next

e83fba5221864cd5943ac747889cbcd0.png

惊喜到了没有,经过两次改良达到了这种效果!  

我是小郑~期待和你一起努力 奔赴热爱勇闯天涯😀

相关文章
|
3月前
|
索引 Python
【Leetcode刷题Python】328. 奇偶链表
在不使用额外空间的情况下,将链表中的奇数和偶数索引节点重新排序的方法,并提供了相应的Python实现代码。
33 0
|
3月前
|
Python
【Leetcode刷题Python】25.K 个一组翻转链表
解决LeetCode "K 个一组翻转链表" 问题的三种方法:使用栈、尾插法和虚拟节点顺序法,并提供了每种方法的Python实现代码。
32 0
|
3月前
|
Python
【Leetcode刷题Python】114. 二叉树展开为链表
LeetCode上114号问题"二叉树展开为链表"的Python实现,通过先序遍历二叉树并调整节点的左右指针,将二叉树转换为先序遍历顺序的单链表。
28 3
【Leetcode刷题Python】114. 二叉树展开为链表
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
54 5
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
41 4
|
3月前
|
存储 Python
【Leetcode刷题Python】23. 合并K个升序链表
合并K个升序链表的方法:使用数组排序的暴力求解法、使用小顶堆的高效方法,以及分而治之的策略,并提供了相应的Python实现代码。
20 1
|
3月前
|
Python
【Leetcode刷题Python】234.回文链表
两种判断链表是否为回文的方法:使用栈和拆分为两个链表后反转对比,并给出了相应的Python代码实现。
24 0
|
4天前
|
存储 数据挖掘 开发者
Python编程入门:从零到英雄
在这篇文章中,我们将一起踏上Python编程的奇幻之旅。无论你是编程新手,还是希望拓展技能的开发者,本教程都将为你提供一条清晰的道路,引导你从基础语法走向实际应用。通过精心设计的代码示例和练习,你将学会如何用Python解决实际问题,并准备好迎接更复杂的编程挑战。让我们一起探索这个强大的语言,开启你的编程生涯吧!
|
10天前
|
机器学习/深度学习 人工智能 TensorFlow
人工智能浪潮下的自我修养:从Python编程入门到深度学习实践
【10月更文挑战第39天】本文旨在为初学者提供一条清晰的道路,从Python基础语法的掌握到深度学习领域的探索。我们将通过简明扼要的语言和实际代码示例,引导读者逐步构建起对人工智能技术的理解和应用能力。文章不仅涵盖Python编程的基础,还将深入探讨深度学习的核心概念、工具和实战技巧,帮助读者在AI的浪潮中找到自己的位置。
下一篇
无影云桌面