[リンクリスト](Link List)の2つのソートリストをマージ

Merge Two Sorted Lists

再帰構造への接続

ここでは、ソートされたリストが重要です.
連結ソートの最後の組合せでは、最初の値から1つずつ比較することで、一度に解決できます.これは、連結ソートの最後の組合せと同じ方法で、最初から比較し、車に戻って簡単に解くことができます.

from typing import List


class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = None


def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    if (not l1) or (l2 and l1.val > l2.val):
        l1, l2 = l2, l1

    if l1:
        l1.next = merge_two_lists(l1.next, l2)
    return l1


if __name__ == "__main__":
    list1 = ListNode(1)
    list2 = ListNode(2)
    list3 = ListNode(4)
    head1 = list1
    list1.next = list2
    list2.next = list3

    list4 = ListNode(1)
    list5 = ListNode(3)
    list6 = ListNode(4)
    head2 = list4
    list4.next = list5
    list5.next = list6

    head = merge_two_lists(head1, head2)
    while head:
        print(head.val, end="")
        if head.next:
            print("->", end="")
        head = head.next

l 1およびl 2は、それぞれ2つの接続リストの最初の値を指す.

l 1とl 2の値を比較して左側に小さい値を表示し、nextは後の値がインターリーブされるように再び呼び出されます.

交換

では、再帰呼び出しを継続して次の値を編成すると、順序は徐々に1つの値に結合され、編成される.最後にl 1はNullになり、つまりコードの中でl 1はNoneになり、再び家に帰ってから車に戻ります.最後にリターンを開始すると、バックトラッキングとなり、織りなす.

短いコードには内容が含まれていて、再帰が含まれているので、難しいです...

参考資料

Pythonアルゴリズムインタビュー