主頁 > 知識庫 > python實現(xiàn)合并兩個有序列表的示例代碼

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

熱門標(biāo)簽:千陽自動外呼系統(tǒng) 平頂山外呼系統(tǒng)免費(fèi) 原裝電話機(jī)器人 400電話申請服務(wù)商選什么 工廠智能電話機(jī)器人 西藏智能外呼系統(tǒng)五星服務(wù) 江蘇客服外呼系統(tǒng)廠家 在哪里辦理400電話號碼 清遠(yuǎn)360地圖標(biāo)注方法

題目描述

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

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服務(wù)器上已經(jīng)封裝了鏈表類,在本地測試時我需要自己來實現(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

遞歸法

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

參考:合并兩個有序鏈表

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

您可能感興趣的文章:
  • python中必會的四大高級數(shù)據(jù)類型(字符,元組,列表,字典)
  • Python列表刪除重復(fù)元素與圖像相似度判斷及刪除實例代碼
  • Python 統(tǒng)計列表中重復(fù)元素的個數(shù)并返回其索引值的實現(xiàn)方法
  • Python基礎(chǔ)詳解之列表復(fù)制
  • Python 把兩層列表展開平鋪成一層(5種實現(xiàn)方式)
  • 淺談Python列表嵌套字典轉(zhuǎn)化的問題
  • Python隨機(jī)函數(shù)random隨機(jī)獲取數(shù)字、字符串、列表等使用詳解
  • Python列表排序方法reverse、sort、sorted詳解
  • Python3 列表list合并的4種方法
  • python獲取指定時間段內(nèi)特定規(guī)律的日期列表
  • python求列表對應(yīng)元素的乘積和的實現(xiàn)
  • Python統(tǒng)計列表元素出現(xiàn)次數(shù)的方法示例
  • python 合并列表的八種方法
  • python 列表元素左右循環(huán)移動 的多種解決方案
  • Python列表排序 list.sort方法和內(nèi)置函數(shù)sorted用法
  • 淺談Python基礎(chǔ)之列表那些事兒

標(biāo)簽:股票 錦州 隨州 安慶 天水 西安 白城 日照

巨人網(wǎng)絡(luò)通訊聲明:本文標(biāo)題《python實現(xiàn)合并兩個有序列表的示例代碼》,本文關(guān)鍵詞  python,實現(xiàn),合并,兩個,有序,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題,煩請?zhí)峁┫嚓P(guān)信息告之我們,我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《python實現(xiàn)合并兩個有序列表的示例代碼》相關(guān)的同類信息!
  • 本頁收集關(guān)于python實現(xiàn)合并兩個有序列表的示例代碼的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章