題目描述
將兩個升序鏈表合并為一個新的升序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(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服務器上已經(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是否為空，如果為空直接返回另一個鏈表即可就不需要進行比較了。如果不為空，我們就需要比較鏈表節(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列表刪除重復元素與圖像相似度判斷及刪除實例代碼
- Python 統(tǒng)計列表中重復元素的個數(shù)并返回其索引值的實現(xiàn)方法
- Python基礎詳解之列表復制
- Python 把兩層列表展開平鋪成一層(5種實現(xiàn)方式)
- 淺談Python列表嵌套字典轉(zhuǎn)化的問題
- Python隨機函數(shù)random隨機獲取數(shù)字、字符串、列表等使用詳解
- Python列表排序方法reverse、sort、sorted詳解
- Python3 列表list合并的4種方法
- python獲取指定時間段內(nèi)特定規(guī)律的日期列表
- python求列表對應元素的乘積和的實現(xiàn)
- Python統(tǒng)計列表元素出現(xiàn)次數(shù)的方法示例
- python 合并列表的八種方法
- python 列表元素左右循環(huán)移動 的多種解決方案
- Python列表排序 list.sort方法和內(nèi)置函數(shù)sorted用法
- 淺談Python基礎之列表那些事兒
