python实现合并两个排序的链表
剑指offer：合并两个排序的链表，Python实现
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
吐槽
本来想用递归实现，但是大脑卡壳，没有想到合适的递归策略，潜意识里还是把两个链表当成两个数组来看待，写出了非递归版本的代码。写完后回看自己写的代码，逻辑不够一目了然，中间变量过多，代码过长，一定不是好代码。上网查阅，发现一个如此美妙的递归版本，哇，写的好美啊！！！看来我对递归的了解和灵活应用还不够啊，至少在链表上还不够啊！！！
解题思路
思路1（非递归，Low）
找到两个链表中头节点值相对更小的链表，将其作为主链表，第二个链表中的元素则不断加入到主链表中。具体策略是：主链表定义两个指针，指向两个相邻的元素。当第二个链表中的元素值小于主链表中第二个指针时，将第二个链表的当前元素插入到主链表两个指针指向的元素中间，并调整指针指向。
Python代码
def Merge(self, pHead1, pHead2): if not pHead1: return pHead2 if not pHead2: return pHead1 mainHead = pHead1 if pHead1.val <= pHead2.val else pHead2 secHead = pHead2 if mainHead == pHead1 else pHead1 mergeHead = mainHead mainNext = mainHead.next while mainNext and secHead: if secHead.val <= mainNext.val: mainHead.next = secHead secHead = secHead.next mainHead.next.next = mainNext mainHead = mainHead.next else: mainHead = mainNext mainNext = mainNext.next if not mainNext: mainHead.next = secHead return mergeHead
思路2（递归版本，Better）
网上找到的Java版本，思路如此清晰，以至于用任何额外的文字描述都显得多余。我用Python重现了思路，代码如下。哎，美妙的代码如此的赏心悦目，流连忘返啊…
def Merge(self, pHead1, pHead2): if not pHead1: return pHead2 if not pHead2: return pHead1 if pHead1.val <= pHead2.val: pHead1.next = self.Merge(pHead1.next, pHead2) return pHead1 else: pHead2.next = self.Merge(pHead1, pHead2.next) return pHead2
最后给出包含测试部分的全部代码：
class Solution: def Merge(self, pHead1, pHead2): if not pHead1: return pHead2 if not pHead2: return pHead1 if pHead1.val <= pHead2.val: pHead1.next = self.Merge(pHead1.next, pHead2) return pHead1 else: pHead2.next = self.Merge(pHead1, pHead2.next) return pHead2 def getNewChart(self, list): if list: node = ListNode(list.pop(0)) node.next = self.getNewChart(list) return node class ListNode: def __init__(self, x): self.val = x self.next = None if __name__ == '__main__': list1 = [1, 3, 5] list2 = [0, 1, 4] testList1 = Solution().getNewChart(list1) testList2 = Solution().getNewChart(list2) final = Solution().Merge(testList1, testList2) while final: print(final.val, end=" ") final = final.next
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。
相关推荐
-
Python实现对特定列表进行从小到大排序操作示例
本文实例讲述了Python实现对特定列表进行从小到大排序操作.分享给大家供大家参考,具体如下: 1.在系统内新建文件rizhireplacelist.txt root@kali:~# cd python/ root@kali:~/python# ls 111.txt listsalaryver2.py readfile2.py rizhireplacelist.txt rizhi.txt tixingexcel.txt
-
Python 按字典dict的键排序,并取出相应的键值放于list中的实例
方法一: def dict_to_numpy_method1(dict): dict_sorted=sorted(dict.iteritems(), key=lambda d:d[0]) results=[value for key,value in dict_sorted] 方法二: def dict_to_numpy_method2(dict): keys=dict.keys() keys.sort() results=[dic[key] for key in keys] 方法三: def
-
python按照多个条件排序的方法
对tuple进行排序,先按照第一个元素升序,如果第一个元素相同,再按照第二个元素降序排列. L = [(12, 12), (34, 13), (32, 15), (12, 24), (32, 64), (32, 11)] L.sort(key=lambda x: (x[0], -x[1])) print(L) 结果: [(12, 24), (12, 12), (32, 64), (32, 15), (32, 11), (34, 13)] 以上这篇python按照多个条件排序的方法就是小编分享给大
-
python爬取酷狗音乐排行榜
本文为大家分享了python爬取酷狗音乐排行榜的具体代码,供大家参考,具体内容如下 #coding=utf-8 from pymongo import MongoClient import time import requests from lxml import etree client = MongoClient() #连接mongo hello = client.hello #连接数据库 user = hello.song #连接表 headers = { 'User-Agent': 'M
-
Python列表常见操作详解(获取,增加,删除,修改,排序等)
本文实例讲述了Python列表常见操作.分享给大家供大家参考,具体如下: 列表是由一系列按特定顺序排列的元素组成的对象.因为列表通常包含多个元素, 所以建议给列表指定一个表示复数的名称. 我们用方括号( [] ) 来表示列表, 并用逗号来分隔其中的元素. types=['娱乐','体育','科技'] print(types) 运行结果: ['娱乐', '体育', '科技'] 可以看到,打印列表的同时,也会将方括号打印出来. 1 获取元素 要获取列表中的某个元素, 在方括号内指定元素的索引即可:
-
python快排算法详解
快排是python经典算法之一. 1.下面讲解的是什么是快排和快排的图示. 2.快排是一种解决排序问题的运算方法. 3.快排的原理:在数组中任意选择一个数字作为基准,用数组的数据和基准数据进行比较,比基准数字打的数字的基准数字的右边,比基准数字小的数字在基准数字的左边, 第一次排序之后分为比基准数据大或比基准数据小两个部分,用刚开始的方法继续排序,直到每个排序分组中只有一个数据或没有数据为止. 4.下面以[ 7 91 23 1 6 3 79 2 ]数组为例子,进行快排运算. 5.选基准:选择数组
-
Python3删除排序数组中重复项的方法分析
本文实例讲述了Python3删除排序数组中重复项的方法.分享给大家供大家参考,具体如下: 给定一个排序数组,你需要在[原地]删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度. 不要使用额外的数组空间,你必须在[原地]修改输入数组并在使用 O(1) 额外空间的条件下完成. 示例 1: 给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2. 你不需要考虑数组中超出新长度后面的元素. 示例 2: 给定 nums =
-
python实现合并两个排序的链表
剑指offer:合并两个排序的链表,Python实现 题目描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 吐槽 本来想用递归实现,但是大脑卡壳,没有想到合适的递归策略,潜意识里还是把两个链表当成两个数组来看待,写出了非递归版本的代码.写完后回看自己写的代码,逻辑不够一目了然,中间变量过多,代码过长,一定不是好代码.上网查阅,发现一个如此美妙的递归版本,哇,写的好美啊!!!看来我对递归的了解和灵活应用还不够啊,至少在链表上还不够啊!!! 解题思路
-
对python实现合并两个排序链表的方法详解
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 1.迭代方法 def Merge(self, pHead1, pHead2): p1, p2 = pHead1, pHead2 if p1 and p2: if p1.val < p2.val: head = p1 p1 = p1.next else: head = p2 p2 = p2.next cur = head elif p1: return p1 else: return p2 while p
-
C++实现合并两个排序的链表
本文实例为大家分享了C++合并两个排序的链表,供大家参考,具体内容如下 问题描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; 方法一 class Solution { public: ListNode* Merge(ListNode* pHead1, ListN
-
java编程题之合并两个排序的链表
本文实例为大家分享了java合并两个排序的链表,供大家参考,具体内容如下 /** * * 剑指offer编程题(JAVA实现)--第16题:合并两个排序的链表 * * 输入两个单调递增的链表,输出两个链表合成后的链表, 当然我们需要合成后的链表满足单调不减规则. * */ public class Test16 { public static ListNode Merge(ListNode list1, ListNode list2) { if (list1 == null) { // 首先判断
-
C++解决合并两个排序的链表问题
目录 题目描述: 示例: 解题思路: 测试代码: 题目描述: 输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的. 数据范围: n为0~1000,节点值为-1000~1000 要求:空间复杂度 O(1),时间复杂度 O(n) 如输入{1,3,5},{2,4,6}时,合并后的链表为{1,2,3,4,5,6},所以对应的输出为{1,2,3,4,5,6},转换过程如下图所示: 或输入{-1,2,4},{1,3,4}时,合并后的链表为{-1,1,2,3,4,4},所
-
TypeScript合并两个排序链表的方法详解
目录 前言 思路分析 实现代码 测试用例 示例代码 前言 给定两个递增排序的链表,如何将这两个链表合并?合并后的链表依然按照递增排序.本文就跟大家分享一种解决方案,欢迎各位感兴趣的开发者阅读本文. 思路分析 经过前面的学习,我们知道了有关链表的操作可以用指针来完成.同样的,这个问题也可以用双指针的思路来实现: p1指针指向链表1的头节点 p2指针指向链表2的头节点 声明一个变量存储合并后的链表,比对两个指针指向的节点值大小: 如果p1指针指向的节点值比p2指向的值小,合并后的链表节点就取p1节点
-
PHP实现合并两个排序链表的方法
本文实例讲述了PHP实现合并两个排序链表的方法.分享给大家供大家参考,具体如下: 问题 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 解决思路 简单的合并排序.由于两个数列本来就是递增的,所以每次将两个数列中较小的部分拿过来就可以了. 实现代码 <?php /*class ListNode{ var $val; var $next = NULL; function __construct($x){ $this->val = $x; } }*/ f
-
Python实现合并两个有序链表的方法示例
本文实例讲述了Python实现合并两个有序链表的方法.分享给大家供大家参考,具体如下: 思路:先选出第一个节点,然后遍历两个链表,把小的作为当前节点的下一个节点,一直到其中一个链表遍历完,这时候把另一个链表直接接上就好 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(obj
-
python实现合并两个有序列表的示例代码
题目描述 将两个升序链表合并为一个新的升序链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的. LeetCode原题地址:https://leetcode-cn.com/problems/merge-two-sorted-lists/ 测试用例 示例1 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例2 输入:l1 = [], l2 = [] 输出:[] 示例3 输入:l1 = [], l2 = [0] 输出:[0] 代码详解 因为Lee
-
python实现合并两个数组的方法
本文实例讲述了python实现合并两个数组的方法.分享给大家供大家参考.具体如下: python合并两个数组,将两个数组连接成一个数组,例如,数组 a=[1,2,3] ,数组 b=[4,5,6],连接后:[1,2,3,4,5,6] 方法1 a=[1,2,3] b=[4,5,6] a=a+b 方法2 a=[1,2,3] b=[4,5,6] a.extend(b) 希望本文所述对大家的Python程序设计有所帮助.