# **Leetcode筆記(Merge Two Sorted Lists)** :::info :information_source: 題目 : Merge Two Sorted Lists, 類型 : linked list , 等級 : easy 日期 : 2023/02/26，2023/05/30，2023/07/01，2023/10/02，2023/12/03，2025/04/02 ::: ### 嘗試 ```python # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: newlist = [] while list1 != None and list2 != None: if list1.val >= list2.val: list1.append() list2.append() else: list1.append() list2.append() list1 = list1.next list2 = list2.next if list1 == None: return list2 if list2 == None: return list1 ``` 2023/05/30 ```python # 要回傳一串list的時候，是要寫一個listnode的next head.next # 自己也要移下一個 list1 = list1.next tail = tail.next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: head = ListNode() tail = head if not list1 and not list2: return None while list1 and list2: if list1.val <= list2.val: tail.next = list1 list1 = list1.next else: tail.next = list2 list2 = list2.next tail = tail.next if not list1 and list2: tail.next = list2 if list1 and not list2: tail.next = list1 return head.next # 回傳的是head.next 不是head ``` 2023/07/01 ```python # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = tail = ListNode() if not list1 and not list2: return None while list1 and list2: if list1.val <= list2.val: tail.next = list1 list1 = list1.next else: tail.next = list2 list2 = list2.next tail = tail.next if list1: tail.next = list1 if list2: tail.next = list2 return dummy.next ``` 2023/10/02 ```python class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: head = ListNode() dummy = head while list1 and list2: if list1.val <= list2.val: dummy.next = list1 list1 = list1.next else: dummy.next = list2 list2 = list2.next dummy = dummy.next if list1: dummy.next = list1 if list2: dummy.next = list2 return head.next ``` 2023/12/03 ```python class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = tail = ListNode() while list1 and list2: if list1.val >= list2.val: tail.next = list2 list2 = list2.next else: tail.next = list1 list1 = list1.next tail = tail.next if list1: tail.next = list1 if list2: tail.next = list2 return dummy.next ``` 2025/04/02 ```python class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = tail = ListNode() while list1 and list2: if list1.val < list2.val: tail.next = list1 list1 = list1.next else: tail.next = list2 list2 = list2.next tail = tail.next if list1: tail.next = list1 list1 = list1.next if list2: tail.next = list2 list2 = list2.next return dummy.next ``` --- ### **優化** 時間複雜度O(n)，空間複雜度O(1) ```python # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() # 建立一個空的node tail = dummy # dummy不會動 會一直在new list的前面 while list1 != None and list2 != None: if list1.val <= list2.val: tail.next = list1 list1 = list1.next else: tail.next = list2 list2 = list2.next tail = tail.next # 若長度不一致 if list1 != None: # list1比較長 tail.next = list1 if list2 != None: tail.next = list2 return dummy.next # 是在dummy下一個的指標才會開始接真正的list ``` --- **:warning: 錯誤語法** :::warning linked list不能.append() tail也要記得換位置tail.next 要考慮兩個list不同長度的情況 ::: **:thumbsup:學習** :::success 建立dummy node= ListNode()，dummy其實類似head，它的next就是 ::: **思路** **講解連結** https://www.youtube.com/watch?v=XIdigk956u0 Provided by. NeetCode ###### tags: `linked list` `easy` `leetcode`