Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

アプローチ

思考

2つのlinked listを確認し、小さい方のものを順に並び替える
whileで2つのlinked listを走査
小さい方のものを取得し、次のリストとして付け足す
両方がNoneになるまで続ける
dummy.nextを返す

実装

class Solution:  
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:  
        dummy = ListNode()  
        cur = dummy  
  
        while list1 and list2:  
            if list1.val < list2.val:  
                cur.next = list1  
                list1 = list1.next  
            else:  
                cur.next = list2  
                list2 = list2.next  
            cur = cur.next  
  
        if list1:  
            cur.next = list1  
        else:  
            cur.next = list2  
  
        return dummy.next

Time Space

注意点

パフォーマンス自体は最適解
可読性自体は改善可能（作ったリストの対応箇所）