【LeetCode】 21. Merge Two Sorted Lists 解答・解説【Python】

はじめに
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python
終わりに

はじめに

ポイント

連結リストを使用した問題です。

この記事で得られること

連結リストを使った初歩的な問題に触れられます。
LeetCode上での連結リストを使った問題の練習になります。

この記事が役立ちそうな方

連結リストに初めて触れる方

連結リストリスト自体が良くわからない方

この記事を読んでもよくわからなかった方は、

最後の項目「疑問が解決しない方はこちらへ」に記載のリンクをどうぞ。

詳細

問題

原文

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

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

1
2

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

Example 2:

Input: list1 = [], list2 = [] Output: []

1
2

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0] Output: [0]

1
2

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

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

-100 <= Node.val <= 100

Both list1 and list2 are sorted in non-decreasing order.

内容(和訳)

2つのソートされた連結リストlist1,list2が与えられます。

2つのリストを1つのソートされたリストとして結合してください。

戻り値となる結合されたリストは2つのリストを結合したものでなければなりません。

結合されたリストのhead(先頭のノード)を返してください。

※正しくない可能性があります。

解答

解答1：Python

# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        #headとtailは同じオブジェクト。一方を変更するともう一方も変化する。浅いコピー
        #headは最後に連結リストの先頭から返すため、tailは連結リストの末尾に次の要素加えるために使用
        head = tail = ListNode(0)
        
        #list1,list2がともに最後の要素まで到達していない限り繰り返す
        while list1 != None and list2 != None:
            #list1の値の方が小さければ
            if list1.val < list2.val:
                #tailの次の要素にlist1を格納。
                #list1.next以降の要素も入るが、次の周回でtail.nextをまた上書きするので良い
                tail.next = list1
                #listは次の要素に進む
                list1 = list1.next
            #list2の値の方が小さければ
            else:
                #tailの次の要素にlist2を格納
                #list2.next以降の要素も入るが、次の周回でtail.nextをまた上書きするので良い
                tail.next = list2
                #list2を次の要素へ進める
                list2 = list2.next
            
            #tailを次の要素へ進める
            tail = tail.next
        
        #list1かlist2が全て追加されたので、残った方のリストを全て加える
        #list全体を指定すると、まとめて代入できる
        tail.next = list1 or list2
        print(head)
        return head.next

# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

#headとtailは同じオブジェクト。一方を変更するともう一方も変化する。浅いコピー

#headは最後に連結リストの先頭から返すため、tailは連結リストの末尾に次の要素加えるために使用

head = tail = ListNode(0)

#list1,list2がともに最後の要素まで到達していない限り繰り返す

while list1 != None and list2 != None:

#list1の値の方が小さければ

if list1.val < list2.val:

#tailの次の要素にlist1を格納。

#list1.next以降の要素も入るが、次の周回でtail.nextをまた上書きするので良い

tail.next = list1

#listは次の要素に進む

list1 = list1.next

#list2の値の方が小さければ

else:

#tailの次の要素にlist2を格納

#list2.next以降の要素も入るが、次の周回でtail.nextをまた上書きするので良い

tail.next = list2

#list2を次の要素へ進める

list2 = list2.next

#tailを次の要素へ進める

tail = tail.next

#list1かlist2が全て追加されたので、残った方のリストを全て加える

#list全体を指定すると、まとめて代入できる

tail.next = list1 or list2

print(head)

return head.next

終わりに

補足・参考・感想

疑問が解決した方はこちらへ

前：121. Best Time to Buy and Sell Stock

次：1822. Sign of the Product of an Array

LeetCode 解答・解説記事一覧

疑問が解決しない方はこちらへ

LeetCodeで初めて連結リストに触れた方は、扱い方がまだ掴めないかもしれません。

LeetCodeでの連結リストについてまとめたのでこちらもどうぞ

解答前に知っておくと役に立つかもしれない情報

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類