Logstash unity algorithm variables mobile pdo flexbox uiwebview Zeptojs jquery选择器找子元素 jquery事件绑定方法 linux自动获取ip cpm计算 mysql升序 leach算法 coreldraw入门学习 git登录命令 matlab图像滤波 math保留两位小数 mysql删除表 python3下载安装 python入门教程 python或运算 python使用正则表达式 javadate java中string java当前时间 java对象序列化 java配置文件 linuxsleep linux硬盘 计算机电子书 网络电视软件下载 神龙kms collect flash制作工具 笔记本测试软件 iframe跨域 小米9截图 pr书写效果
当前位置: 首页 > 学习教程  > 编程语言

合并两个有序链表-链表21

2021/2/13 17:19:14 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

Python 思路 我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时,判断 l1 和 l2 哪一个链表的头节点的值更小,将较小值的节点添加到结果里,当一个节点被添加到结果里之后,将对应链表中的节点向后移一位。 算法 …

Python

思路

我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时,判断 l1 和 l2 哪一个链表的头节点的值更小,将较小值的节点添加到结果里,当一个节点被添加到结果里之后,将对应链表中的节点向后移一位。

算法

首先,我们设定一个哨兵节点 prehead ,这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针,我们需要做的是调整它的 next 指针。然后,我们重复以下过程,直到 l1 或者 l2 指向了 null :如果 l1 当前节点的值小于等于 l2 ,我们就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。否则,我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面,我们都需要把 prev 向后移一位。

在循环终止的时候, l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的,所以不管哪个链表是非空的,它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面,并返回合并链表即可。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1, l2):
        
        prehead = ListNode(100)
        prev = prehead
        
        while(True):
            if l1 and l2:
                if l1.val <= l2.val:
                    prev.next = l1
                    l1 = l1.next
                else:
                    prev.next = l2
                    l2 = l2.next
            else:
                if l1:
                    prev.next = l1
                    break
                else:
                    prev.next = l2
                    break
            prev = prev.next
        
        return prehead.next

复杂度分析:

  • 时间复杂度:O(n + m),其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中,l1 和 l2 只有一个元素会被放进合并链表中,因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的,因此总的时间复杂度为O(n+m)。
  • 空间复杂度:O(1)。我们只需要常数的空间存放若干变量。

本文链接: http://www.dtmao.cc/news_show_700119.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?