[LeetCode] Merge Two Sorted Lists - Python

Algorithm Problem with Python — 39day

問題の説明📖

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.
2つのソートされたリンクのリストを集計し、ソートされたリストに戻します.最初の2つのリストのノードを分割してリストを作成する必要があります.
I/O例
Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: l1 = [], l2 = []
Output: []
Example 3:
Input: l1 = [], l2 = [0]
Output: [0]
せいげんじょうけん

The number of nodes in both lists is in the range [0, 50].

-100 <= Node.val <= 100

Both l1 and l2 are sorted in non-decreasing order.

問題を理解する🔑

入力順に並べ替えられた2つの接続リスト(ex[1,2,4],[1,3,4]).
この問題では、ソートリストが重要です.
[連結ソート](Merge Sort)では、最初の値から順番に比較します.この問題は、[連結ソート](Merge Sort)の最後の組み合わせと同じで、最初の値から比較し、戻って簡単に解決できます.

首都コード▼▼

交換値は

のputl 1およびl 2であり、左側に小さな値が現れるようにした.

l1.nextは再帰コールを使用して次の値を記述します.

l 1がNoneになって復帰

コード作成

# 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, l1: ListNode, l2: ListNode) -> ListNode:
        # print('l1',l1) # l1 ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 4, next: None}}}
        # print('l2',l2) # l2 ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}
        if (not l1) or (l2 and l1.val > l2.val):
            l1, l2 = l2, l1
        if l1:
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1

整理する😄

この問題で使用する「マージソート」(merge sort)は、1つのリストを2つの等しいサイズのリストに分割し、分割された部分リストをソートし、2つのソートされた部分リストをマージして、リスト全体をソートされたリストにします.
Reference

朴尚吉、『Pythonアルゴリズムインタビュー』、シューマン(2020)、p 213-218.

HeeJeong Kwon,"アルゴリズム"マージソート(merge sort)