[LeetCode] #21. Merge Two Sorted Lists
題目
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
直覺解
構想：
做一個 dummy head，比較小的節點先接上去。
python 3 實作：
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 and not l2:
return None
dummy = ListNode()
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
while l1:
current.next = l1
current = current.next
l1 = l1.next
while l2:
current.next = l2
current = current.next
l2 = l2.next
current.next = None
head = dummy.next
dummy.next = None
return head
效能：
第一次：
Runtime: 28 ms, faster than 98.17% of Python3 online submissions for Merge Two Sorted Lists.
Memory Usage: 14.3 MB, less than 32.13% of Python3 online submissions for Merge Two Sorted Lists.
第二次：
Runtime: 36 ms, faster than 77.45% of Python3 online submissions for Merge Two Sorted Lists.
Memory Usage: 14.2 MB, less than 62.50% of Python3 online submissions for Merge Two Sorted Lists.
參考別人的解
來源：
研究重點：更簡潔的寫法。
優化自己的 python 3 實作：
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1: return l2
if not l2: return l1
dummy = ListNode()
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 or l2
current = dummy.next
dummy.next = None
return current
效能：
Runtime: 40 ms, faster than 50.53% of Python3 online submissions for Merge Two Sorted Lists.
Memory Usage: 14.2 MB, less than 85.58% of Python3 online submissions for Merge Two Sorted Lists.
參考別人的解
來源：
sample 20 ms submission：
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 or not l2:
return l1 or l2
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
研究重點：recursion 寫法。
研究感想
不需要自己做 dummy head 了，直接拿 val 最小的那個節點來改裝。每次的 recursion 只負責從兩個節點的頭之中挑出最小的那個頭，然後把「尋找 next」的任務交棒給另一個 mergeTwoLists。
Comments
Post a Comment