如何在python中合并两个有序列表

本篇文章给大家分享的是有关如何在python中合并两个有序列表，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。

测试用例

示例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 l1l1 = 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.nextl1 = 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中合并两个有序列表，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注编程网行业资讯频道。