LoginSignup
1
1

More than 1 year has passed since last update.

@marupy

21. Merge Two Sorted Lists Easyの解説

Last updated at Posted at 2022-05-27

問題文：
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が読み込まれて下層から上層に戻って値が返されていく。

  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が代入されて、

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

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1