python實(shí)現(xiàn)合并兩個(gè)有序列表的示例代碼
題目描述
將兩個(gè)升序鏈表合并為一個(gè)新的升序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。
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]
代碼詳解
因?yàn)長eetCode服務(wù)器上已經(jīng)封裝了鏈表類，在本地測試時(shí)我需要自己來實(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
遞歸法
遞歸法的思路比較簡單，我們需要先判斷鏈表l1和鏈表l2是否為空，如果為空直接返回另一個(gè)鏈表即可就不需要進(jìn)行比較了。如果不為空，我們就需要比較鏈表節(jié)點(diǎn)的值誰的更大，如果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è)算法更簡單了，我們只需要遍歷鏈表l1和l2然后再比較大小即可，對(duì)于最后沒遍歷完的部分，直接追加到合并鏈表的后面即可。
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
#用來合并鏈表
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)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Python函數(shù)isalnum用法示例小結(jié)
isalnum()函數(shù)是Python中的一個(gè)內(nèi)置函數(shù),用于判斷字符串是否只由數(shù)字和字母組成,其內(nèi)部實(shí)現(xiàn)原理比較簡單,只需遍歷字符串中的每一個(gè)字符即可,這篇文章主要介紹了Python函數(shù)isalnum用法介紹,需要的朋友可以參考下2024-01-01
在django admin詳情表單顯示中添加自定義控件的實(shí)現(xiàn)
這篇文章主要介紹了在django admin詳情表單顯示中添加自定義控件的實(shí)現(xiàn)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-03-03
這篇文章主要介紹了Django框架之django admin的命令行知識(shí),文中通過示例代碼給大家介紹的非常詳細(xì)，需要的朋友可以參考下2021-09-09
這篇文章主要介紹了玩彩票贏錢概率有多少？用Python來告訴你,需要的朋友可以參考下2019-06-06
zip()是Python的一個(gè)內(nèi)建函數(shù)，它接受一系列可迭代的對(duì)象作為參數(shù)，將對(duì)象中對(duì)應(yīng)的元素打包成一個(gè)個(gè)tuple（元組），然后返回由這些tuples組成的list（列表）。這篇文章主要介紹了python中的 zip函數(shù)詳解及用法舉例,需要的朋友可以參考下2020-02-02
這篇文章主要介紹了基于python圖像處理API的使用示例，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-04-04
python將字典內(nèi)容存入mysql實(shí)例代碼
這篇文章主要介紹了python將字典內(nèi)容存入mysql實(shí)例代碼，具有一定借鑒價(jià)值,需要的朋友可以參考下2018-01-01
python代碼實(shí)現(xiàn)小程序登錄流程時(shí)序總結(jié)
這篇文章主要為大家介紹了python代碼實(shí)現(xiàn)小程序的登錄案例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步早日升職加薪2022-04-04
Python3.5實(shí)現(xiàn)的三級(jí)菜單功能示例
這篇文章主要介紹了Python3.5實(shí)現(xiàn)的三級(jí)菜單功能,涉及Python針對(duì)json格式數(shù)據(jù)的讀取、遍歷、查找、判斷等相關(guān)操作技巧,需要的朋友可以參考下2019-03-03
這篇文章主要介紹了jupyter實(shí)現(xiàn)重新加載模塊，具有很好的價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-04-04