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

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服務器上已經封裝了鏈表類，在本地測試時我需要自己來實現鏈表類，代碼如下

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 = nodehead = 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 = l2l2 = l2.next else:pre.next = l1l1 = 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實現合并兩個有序列表的示例代碼的文章就介紹到這了,更多相關python 合并兩個有序列表內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網！