题目描述
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
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]
代码详解
因为LeetCode服务器上已经封装了链表类，在本地测试时我需要自己来实现链表类，代码如下
class ListNode:
def __init__(self, val, next=None):
if isinstance(val,int):
self.val = val
self.next = next
elif isinstance(val,list):
self.val = val[0]
self.next = None
head = self
for i in range(1,len(val)):
node = ListNode(val[i],None)
head.next = node
head = head.next
递归法
递归法的思路比较简单，我们需要先判断链表l1和链表l2是否为空，如果为空直接返回另一个链表即可就不需要进行比较了。如果不为空，我们就需要比较链表节点的值谁的更大，如果l1大于l2我们就更改链表l2的下一个节点，然后再比较l2的下一个节点和l1，反之可得另一种情况的处理方法。
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
#如果链表l1为None直接返回链表l2即可
if l1 is None:
return l2
#如果链表l2为None直接返回链表l1即可
elif l2 is None:
return l1
#如果链表l1大于链表l2
elif l1.val > l2.val:
#更改链表l2下一个节点的指向
l2.next = self.mergeTwoLists(l1,l2.next)
return l2
else:
#更改链表l1下一个节点的指向
l1.next = self.mergeTwoLists(l1.next,l2)
return l1
l1 = ListNode([1,2,4])
l2 = ListNode([1,3,4])
s = Solution()
l = s.mergeTwoLists(l1,l2)
while l:
print(l.val)
l = l.next
遍历法
这个算法更简单了，我们只需要遍历链表l1和l2然后再比较大小即可，对于最后没遍历完的部分，直接追加到合并链表的后面即可。
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
#用来合并链表
prehead = ListNode(-1)
#创建一个哨兵节点
pre = prehead
while l1 and l2:
if l1.val > l2.val:
pre.next = l2
l2 = l2.next
else:
pre.next = l1
l1 = l1.next
#更改哨兵节点的下一个指向
pre = pre.next
pre.next = l1 if l1 else l2
return prehead.next
l1 = ListNode([1,2,4])
l2 = ListNode([1,3,4])
s = Solution()
l = s.mergeTwoLists(l1,l2)
while l:
print(l.val)
l = l.next
参考：合并两个有序链表
到此这篇关于python实现合并两个有序列表的示例代码的文章就介绍到这了,更多相关python 合并两个有序列表内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！
您可能感兴趣的文章:- python中必会的四大高级数据类型（字符,元组,列表,字典）
- Python列表删除重复元素与图像相似度判断及删除实例代码
- Python 统计列表中重复元素的个数并返回其索引值的实现方法
- Python基础详解之列表复制
- Python 把两层列表展开平铺成一层(5种实现方式)
- 浅谈Python列表嵌套字典转化的问题
- Python随机函数random随机获取数字、字符串、列表等使用详解
- Python列表排序方法reverse、sort、sorted详解
- Python3 列表list合并的4种方法
- python获取指定时间段内特定规律的日期列表
- python求列表对应元素的乘积和的实现
- Python统计列表元素出现次数的方法示例
- python 合并列表的八种方法
- python 列表元素左右循环移动 的多种解决方案
- Python列表排序 list.sort方法和内置函数sorted用法
- 浅谈Python基础之列表那些事儿
