Skip to main content

0021 - Merge Two Sorted Lists

大意

就是把已經排序的兩個 LinkedList 合併到一個 LinkedList,且要保持順序

實際作法

由於自己做出來都是 Timeout,應該是哪裡做錯了,以下附上正確的 Code:

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        
        head = ListNode()
        current = head

        while list1 != None and list2 != None:
            if list1.val <= list2.val:
                current.next = list1
                temp = list1.next
                current = list1
                list1 = temp
            else:
                current.next = list2
                temp = list2.next
                current = list2
                list2 = temp
        
        if list1 != None:
            current.next = list1
        if list2 != None:
            current.next = list2

        return head.next

建立一個新的 LIstNode 當作假的起頭(真正的起頭在假起頭的下一個),然後去比較兩個當前  ListNode 代表的數字

  • 如果  list1 的數字比較小,或等於 list2,則新  list 的 next 必須是 list1
  • 然後原本  list1 換成 list1 的下一個,也就是 list1.next
  • 否則,新 list 的 next 必須為 list2,然後原本 list2 換成 list2.next
  • 以此類推,直到  list1 或 list2 其中一個的值是 None (null)
  • 但是 list1 或 list2 無論剩餘 LinkedList 的 Node 數量有多少,只要其中一個不是 None (null),就直接接到新 ListNode 的最後就好(畢竟都排序過了)

然後回傳假的起頭的下一個,就是排序好的 LinkedList!