21. Merge Two Sorted Lists Easyの解説

>問題文：
https://leetcode.com/problems/merge-two-sorted-lists/
正解者さん：**Mr.StefanPochmann**
https://leetcode.com/problems/merge-two-sorted-lists/discuss/9771/Simple-5-lines-Python
```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の解説
```python:関数の引数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された単方向リストになっている。
```python:
list1 = ListNode{val: 1, next: ListNode{val: 2, next: None}}
list2 = ListNode{val: 1, next: ListNode{val: 3, next: None}}
```
いかに単方向リストをくっつけるかが問題となる。
## ②if notの解説
```python: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に値が入り続ける。
## ③再帰関数の解説
```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
```
＞＞＞list1がNoneになるまで、self.mergeTwoLists(list1.next, list2)が繰り返される行。
つまり、もしlist1の中身がある場合、この層のlist1.nextに、self.mergeTwoLists(list1.next, list2)からreturnされる下層のlist1の値が代入される。
　　
　　
ここからは分かりやすくするために、単方向リスト内の値をprintしながら説明していく。
```python: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)が実行されて、
下層に潜り込んでいく。(再帰関数)
```python:第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層に移動します.
```

```python:第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層に移動します.
```

```python:第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層に移動します.
```

```python:第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層に移動します.
```

```python:第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が読み込まれて下層から上層に戻って値が返されていく。
>1. 最下層の第4層でif list1:が呼ばれなくなった。
>2. 今までself.mergeTwoLists(list1.next, list2)に何回も潜り込んだまま、
読み込みが到達していなかったreturn list1が読み込めるようになった。
>3. 1つ上の第3層のlist1.next = self.mergeTwoLists(list1.next, list2)に、
第4層のreturn list1の値が入る。
>4. 1つ上の層の単方向リストのnextに、どんどん下層のlist1が代入されていく。
>5. 終わり。

　　
第3層のlist1 = ListNode{val: 3, next: None}のlist1.nextに、
第4層のlist1 = Noneが代入されて、
```python:第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}が代入されて、
```python:第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のこと。
　　
　　
以下、繰り返し。
```python:第1層
>>>return list1の値がlist.nextに代入されました.

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

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

```python:第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も再帰関数も知らなくて、はやくも解けない解答が来たか…と挫折しそうになった。
ただ、今回の記事作成で読めるようになったので、少しだけ嬉しい。