問題文：
https://leetcode.com/problems/merge-two-sorted-lists/
正解者さん：Mr.StefanPochmann
https://leetcode.com/problems/merge-two-sorted-lists/discuss/9771/Simple-5-lines-Python

正解の引用コード

# 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):
        if not list1 or list2 and list1.val > list2.val:
            list1, list2 = list2, list1
        if list1:
            list1.next = self.mergeTwoLists(list1.next, list2)
        return list1

【2つのlinked listを再帰関数で結合する】

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

①list1、list2の解説

関数の引数list1、list2

# 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):
        if not list1 or list2 and list1.val > list2.val:
            list1, list2 = list2, list1
        if list1:
            list1.next = self.mergeTwoLists(list1.next, list2)
        return list1

＞＞＞この問題では、既にlist1とlist2はsortされた単方向リストになっている。

list1 = ListNode{val: 1, next: ListNode{val: 2, next: None}}
list2 = ListNode{val: 1, next: ListNode{val: 3, next: None}}

いかに単方向リストをくっつけるかが問題となる。

②if notの解説

list1、list2

# 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):
＞＞＞  if not list1 or list2 and list1.val > list2.val:
＞＞＞      list1, list2 = list2, list1
        if list1:
            list1.next = self.mergeTwoLists(list1.next, list2)
        return list1

＞＞＞もしもlist1が空だった場合、
または、list2の中身があって、list1の0番目の値がlist2の0番目の値よりも大きかった場合、
list1とlist2をまるまる入れ替える。という行である。
これは、のちに出てくるlist1.next = self.mergeTwoLists(list1.next, list2)にも深く関わっている。　

【主な役割】
‣inputのlist内が空でも対応できる。
‣より小さい値をlist1に入れることができる。
‣再帰されてもlist1に値が入り続ける。

③再帰関数の解説

再帰関数、単方向リストの結合場所

# 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):
        if not list1 or list2 and list1.val > list2.val:
            list1, list2 = list2, list1
＞＞＞  if list1:
＞＞＞      list1.next = self.mergeTwoLists(list1.next, list2)
        return list1

＞＞＞list1がNoneになるまで、self.mergeTwoLists(list1.next, list2)が繰り返される行。
つまり、もしlist1の中身がある場合、この層のlist1.nextに、self.mergeTwoLists(list1.next, list2)からreturnされる下層のlist1の値が代入される。
　　
　　
ここからは分かりやすくするために、単方向リスト内の値をprintしながら説明していく。

printの位置

# 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):
＞＞＞  print(list1,list2,list1.val,list2.val,list1.next,list2.next)
        if not list1 or list2 and list1.val > list2.val:
            list1, list2 = list2, list1
        if list1:
            list1.next = self.mergeTwoLists(list1.next, list2)
        return list1

　　
　　
ここから、何度もself.mergeTwoLists(list1.next, list2)が実行されて、
下層に潜り込んでいく。(再帰関数)

第0層(一番上)

#print(list1,list2,list1.val,list2.val,list1.next,list2.next)

>>>class Solution(object):
    def mergeTwoLists(self, list1, list2):が実行されました.

list1 = ListNode{val: 1, next: ListNode{val: 2, next: None}}
list2 = ListNode{val: 1, next: ListNode{val: 3, next: None}}
list1.val = 1
list2.val = 1
list1.next = ListNode{val: 2, next: None}
list2.next = ListNode{val: 3, next: None}

>>>if list1:
     list1.next = self.mergeTwoLists(list1.next, list2)が実行されました.
第1層に移動します.

第1層

#self.mergeTwoLists(list1.next, list2)

list1 = ListNode{val: 2, next: None}
list2 = ListNode{val: 1, next: ListNode{val: 3, next: None}}
list1.val = 2
list2.val = 1
list1.next = None
list2.next = ListNode{val: 3, next: None}

>>>list1, list2 = list2, list1が実行されました.

list1 = ListNode{val: 1, next: ListNode{val: 3, next: None}}
list2 = ListNode{val: 2, next: None}
list1.val = 1
list2.val = 2
list1.next = ListNode{val: 3, next: None}
list2.next = None

>>>if list1:
     list1.next = self.mergeTwoLists(list1.next, list2)が実行されました.
第2層に移動します.

第2層

#self.mergeTwoLists(list1.next, list2)

list1 = ListNode{val: 3, next: None}
list2 = ListNode{val: 2, next: None}
list1.val = 3
list2.val = 2
list1.next = None
list2.next = None

>>>list1, list2 = list2, list1が実行されました.

list1 = ListNode{val: 2, next: None}
list2 = ListNode{val: 3, next: None}
list1.val = 3
list2.val = 2
list1.next = None
list2.next = None

>>>if list1:
     list1.next = self.mergeTwoLists(list1.next, list2)が実行されました.
第3層に移動します.

第3層

#self.mergeTwoLists(list1.next, list2)

list1 = None
list2 = ListNode{val: 3, next: None}
list1.val = 
list2.val = 3
list1.next = None
list2.next = None

>>>list1, list2 = list2, list1が実行されました.

list1 = ListNode{val: 3, next: None}
list2 = None
list1.val = 3
list2.val = None
list1.next = None
list2.next = None

>>>if list1:
     list1.next = self.mergeTwoLists(list1.next, list2)が実行されました.
第4層に移動します.

第4層

#self.mergeTwoLists(list1.next, list2)

list1 = None
list2 = None
list1.val = None
list2.val = None
list1.next = None
list2.next = None

>>>return list1が実行されました.

list1 = None

第4層でlist1がNoneになったため、
if list1:
list1.next = self.mergeTwoLists(list1.next, list2)が実行されなくなった。

これ以上関数が呼ばれなくなったので、次は、ずっと保留されていた最後の行にあるreturn list1が読み込まれて下層から上層に戻って値が返されていく。

最下層の第4層でif list1:が呼ばれなくなった。

今までself.mergeTwoLists(list1.next, list2)に何回も潜り込んだまま、
読み込みが到達していなかったreturn list1が読み込めるようになった。

1つ上の第3層のlist1.next = self.mergeTwoLists(list1.next, list2)に、
第4層のreturn list1の値が入る。

1つ上の層の単方向リストのnextに、どんどん下層のlist1が代入されていく。

終わり。

　　
第3層のlist1 = ListNode{val: 3, next: None}のlist1.nextに、
第4層のlist1 = Noneが代入されて、

第3層

>>>return list1の値がlist.nextに代入されました.

>>>return list1が実行されました.

list1 = ListNode{val: 3, next: None}

第3層は、
list1 = ListNode{val: 3, next: None}となった。
　　
　　
次は、第2層のlist1 = ListNode{val: 2, next: None}のlist1.nextに、
第3層のlist1 = ListNode{val: 3, next: None}が代入されて、

第2層

>>>return list1の値がlist.nextに代入されました.

>>>return list1が実行されました.

list1 = ListNode{val: 2, next: ListNode{val: 3, next: None}}

第2層は、
list1 = ListNode{val: 2, next: ListNode{val: 3, next: None}}となった。
　　
　　
ちなみに、list1.nextというのは、
list1 = ListNode{val: x, next: ...}
一番左側にある最初のnextのこと。
　　
　　
以下、繰り返し。

第1層

>>>return list1の値がlist.nextに代入されました.

>>>return list1が実行されました.

list1 = ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: None}}}

第0層(一番上)

>>>return list1の値がlist.nextに代入されました.

>>>return list1が実行されました.

list1 = ListNode{val: 1, next: ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: None}}}

最終的に、list1の値は[1,1,2,3]となった。
　　
　　
これを最初に見た時に、「簡単なコードにまとめてるんだなあ。」と思ったけれど、
よくよく読んだらかなり複雑だった。
しかも、linked listも再帰関数も知らなくて、はやくも解けない解答が来たか…と挫折しそうになった。
ただ、今回の記事作成で読めるようになったので、少しだけ嬉しい。