[leetcode algorithms]題目21

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4Output: 1->1->2->3->4->4

自己寫的代碼：

取l1和l2的首個元素的較大者，直至l1和l2都變空。運行時間83 ms

class Solution: def cmp(self, l1, l2): if l2 is None: return True if l1 is None: return False return l1.val < l2.val def mergeTwoLists(self, l1, l2): if l1 == []: return l2 if l2 == []: return l1 node = ListNode(None) tmp = node while l1 or l2: if self.cmp(l1, l2): tmp.next = l1 l1 = l1.next else: tmp.next = l2 l2 = l2.next tmp = tmp.next return node.next

討論區的優秀代碼：

和l2的首個元素的較大者，直至l1或l2都變空，然後把沒空的list再append過來，比我的代碼更加簡潔

def mergeTwoLists1(self, l1, l2): head = tail = ListNode(0) while l1 and l2: if l1.val<=l2.val: tail.next = l1 l1 = l1.next else: tail.next = l2 l2 = l2.next tail = tail.next tail.next = l1 if l1 else l2 # a better way is tail.next = l1 or l2, as in OPs code return head.next

推薦閱讀：