LeetCode刷题之合并排序链表
2018-06-18 02:11:42来源：未知 阅读 ()
合并两个有序链表并返回一个新的列表。新列表应该由连接在一起的节点前两个列表
给定实例:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
思路分析:
引入第三个链表，存储合并之后的链表，开两个指针，分别遍历两个链表，当遍历到一个节点的时候，就开始判断大小，然后将小的链表节点存储到第三个链表中，依次递归判断。但是我们需要考虑临界条件，如果第一个链表的数都比第二个链表的小，那么我们就直接将第二个链表链接到第三个链表的next域中就行。
代码如下:
class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def mergeTwoLists(self, l1, l2): if l1 is None: return l2 if l2 is None: return l1 pMerge = ListNode(None) if l1.val < l2.val: pMerge = l1 pMerge.next = self.mergeTwoLists(l1.next, l2) else: pMerge = l2 pMerge.next = self.mergeTwoLists(l1, l2.next) return pMerge
分析下开销: 额外的内存是引入的第三个链表，而空间大小就是O(n)。此外就没有了，时间复杂度就是递归所花费的时间。
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
- LeetCode链表简单题 2019-07-24
- 20190516-归并排序 2019-05-17
- pandas的合并、连接、去重、替换 2019-05-08
- pandas(三) 2019-04-11
- python两个列表合并为字典，一个作为key，一个作为value 2019-04-11
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
