合并兩個有序連結清單
“Think ahead. Don't let day-to-day operations drive out planning.” — Donald Rumsfeld
題目描述
輸入兩個單調遞增的連結清單，輸出兩個連結清單合成後的連結清單，當然我們需要合成後的連結清單滿足遞增有序的規則。
示例1：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4 複制
限制：
0 <= 連結清單長度 <= 1000 複制
解題思路一：遞歸法
- 由于連結清單是升序排列，如果連結清單1的頭結點小于連結清單2的頭結點的值，那麼連結清單1的頭結點就是合并後連結清單的頭結點。
- 并将下一層遞歸函數的傳回值，連結到目前結點的尾部。
- 遞歸終止條件：至少一個為空，傳回剩下的那個
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 == None:
return l2
if l2 == None:
return l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2 複制
解題思路二：雙指針比較
分别用指針l1, l2來周遊兩個連結清單，如果目前l1指向的資料小于l2指向的資料，則将l1指向的結點歸入合并後的連結清單，否則将l2指向的結點歸并到合并的連結清單中。
如果有一個連結清單周遊結束後，則把未結束的連結清單連接配接到合并連結清單後的連結清單尾部。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 == None:
return l2
if l2 == None:
return l1
if l1.val >= l2.val:
head = l2
l2 = l2.next
else:
head = l1
l1 = l1.next
cur = head
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
cur = cur.next
l1 = l1.next
else:
cur.next = l2
cur = cur.next
l2 = l2.next
if l1 == None and l2:
cur.next = l2
elif l2 == None and l1:
cur.next = l1
return head 複制
解題思路三：虛拟頭結點
解題思想跟上述一樣，但是為了減少對每一個節點的不同情況進行考慮，可以考慮建立一個虛拟頭結點dummy（這是一個很常用的連結清單題的技巧），然後用一個真正在走的結點cur指向這個dummy，每一個cur都會選取正确的之連接配接在以dummy為頭結點的連結清單上。
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = cur = ListNode(0)
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next 複制
時間複雜度:
，m,n分别為連結清單l1, l2的長度
空間複雜度:
感謝你的閱讀，這裡是不斷學習中的yuzhou1su，keep coding, keep loving。