1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

【LeetCode】就活に向けたコーディングテスト対策 #07

Last updated at Posted at 2021-06-17

#はじめに
こんばんは.
M1就活生がLeetCodeから,easy問題を中心にPythonを用いて解いていきます.

↓では,解いた問題のまとめを随時更新しています.
まとめ記事

#問題
今回解いたのは,難易度easyから 問題21のMerge Two Sorted Lists です.
問題としては,ソートされたl1l2をマージして,それらをソートしたリストとして返すというもの.この際,l1l2と返却値であるソートしたリストには,次のようなクラス指定があります.

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

入力例と出力例は以下の通りです.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: l1 = [], l2 = []
Output: []

Example 3:

Input: l1 = [], l2 = [0]
Output: [0]

#書いたコード
今回の問題では,再帰を使って書いてみました.
まずはじめに,片方のリストが空であれば,もう片方を返します.このとき,入力されるl1l2はもともとソートされているので,今回の問題ではこのまま返すことができます.
次に,l1l2の先頭要素を比較します.l1の方が小さければ,l1.nextl2を入力として再帰呼び出しすることで,l1を前進させます.同様に,l2の方が小さければ,l1l2.nextを入力として再帰呼び出しすることで,l2を前進させます.このとき,最終的には小さい値を最初の要素とするため,再帰呼び出し後,小さい方のリストを返します.

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2
        if not l2:
            return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

再帰を使わない方法での解法があったので,参考に書いてみました.
まず,マージするリストの先頭であるdummyと,どの値をdummyに追加すべきかを探すためのtmpを初期化します.
l1l2がどちらも空でない場合に,l1l2の先頭要素を比較します.どちらか一方が空の場合は,もう片方を返すようにするためです.l1l2tmpを進めていくことで,マージしたリストを作っていきます.

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    dummy = tmp = ListNode()
    while l1 and l2:
        if l1.val < l2.val:
            tmp.next = l1
            l1 = l1.next
        else:
            tmp.next = l2
            l2 = l2.next
        tmp = tmp.next
    tmp.next = l1 or l2
    return dummy.next

#おわりに
今回の問題は入力値,返却値の型指定など今までにないパターンだったので,色々と調べながら試行錯誤してみました.
pythonのコピーは癖があるものの,今回のような使い方もできるのかと勉強になりました.

今回書いたコードはGitHubにもあげておきます.

前回 次回

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
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?