python實(shí)現(xiàn)合并兩個(gè)有序列表的示例代碼

更新時(shí)間：2021年04月01日 10:41:56 作者：修煉之路

這篇文章主要介紹了python實(shí)現(xiàn)合并兩個(gè)有序列表的示例代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

題目描述

將兩個(gè)升序鏈表合并為一個(gè)新的升序鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

LeetCode原題地址：https://leetcode-cn.com/problems/merge-two-sorted-lists/

測(cè)試用例

示例1

在這里插入圖片描述

輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]

示例2

輸入：l1 = [], l2 = []
輸出：[]

示例3

輸入：l1 = [], l2 = [0]
輸出：[0]

代碼詳解

因?yàn)長(zhǎng)eetCode服務(wù)器上已經(jīng)封裝了鏈表類，在本地測(cè)試時(shí)我需要自己來(lái)實(shí)現(xiàn)鏈表類，代碼如下

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

遞歸法

遞歸法的思路比較簡(jiǎn)單，我們需要先判斷鏈表l1和鏈表l2是否為空，如果為空直接返回另一個(gè)鏈表即可就不需要進(jìn)行比較了。如果不為空，我們就需要比較鏈表節(jié)點(diǎn)的值誰(shuí)的更大，如果l1大于l2我們就更改鏈表l2的下一個(gè)節(jié)點(diǎn)，然后再比較l2的下一個(gè)節(jié)點(diǎn)和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下一個(gè)節(jié)點(diǎn)的指向
      l2.next = self.mergeTwoLists(l1,l2.next)
      return l2
    else:
      #更改鏈表l1下一個(gè)節(jié)點(diǎn)的指向
      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

遍歷法

這個(gè)算法更簡(jiǎn)單了，我們只需要遍歷鏈表l1和l2然后再比較大小即可，對(duì)于最后沒(méi)遍歷完的部分，直接追加到合并鏈表的后面即可。

class Solution:
  def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    #用來(lái)合并鏈表
    prehead = ListNode(-1)
    #創(chuàng)建一個(gè)哨兵節(jié)點(diǎn)
    pre = prehead
    while l1 and l2:
      if l1.val > l2.val:
        pre.next = l2
        l2 = l2.next
      else:
        pre.next = l1
        l1 = l1.next
      #更改哨兵節(jié)點(diǎn)的下一個(gè)指向
      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

參考：合并兩個(gè)有序鏈表

到此這篇關(guān)于python實(shí)現(xiàn)合并兩個(gè)有序列表的示例代碼的文章就介紹到這了,更多相關(guān)python 合并兩個(gè)有序列表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: