ゼロから始めるLeetCode Day24 「21. Merge Two Sorted Lists」

#概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day23「226. Invert Binary Tree」

基本的にeasyのacceptanceが高い順から解いていこうかと思います。

Twitterやってます。

問題

21. Merge Two Sorted Lists

二つのソートされた連結リストが与えられるので、それらをマージし、新しいリストを返します。

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

解法

そろそろ反復法を使って解いてみたかったので今回は再帰と反復法を使った解き方の二つを載せています。

まずは再帰です。

# 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, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 or not l2:
            return l1 or l2
        if l1.val >= l2.val:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2
        else:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
# Runtime: 32 ms, faster than 89.62% of Python3 online submissions for Merge Two Sorted Lists.
# Memory Usage: 13.8 MB, less than 6.61% of Python3 online submissions for Merge Two Sorted Lists.

シンプルにまとまっていて非常に読みやすいので私は再帰の方が好きです。
書く側が楽なのもありますし。

続いて反復法で書いてみた例です。

# 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, l1: ListNode, l2: ListNode) -> ListNode:
        temp = ans = ListNode(0)
        while l1 or l2:
            if l1 and l2:
                if l1.val < l2.val:
                    ans.next = l1
                    l1 = l1.next
                else:
                    ans.next = l2
                    l2 = l2.next
            elif l1:
                ans.next = l1
                l1 = l1.next
            elif l2:
                ans.next = l2
                l2 = l2.next
            ans = ans.next
        return temp.next

# Runtime: 28 ms, faster than 97.54% of Python3 online submissions for Merge Two Sorted Lists.
# Memory Usage: 13.9 MB, less than 6.61% of Python3 online submissions for Merge Two Sorted Lists.

基本的な考え方は特定の要素が存在する間、条件分岐で処理をしていく、というものです。
今回の例だとListNodeのl1とl2が存在する間処理を続け、仮に両方とも存在するのであれば値の比較をして小さい方を最終的に返すansに代入、そして要素がなくなった方のListNodeの要素を一つ後ろにずらせば良いのでこのような書き方になりました。

これだとどんな人にもわかりやすいですが、同時に少し冗長に感じてしまうと思います。
なので書き換えてみました。

# 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, l1: ListNode, l2: ListNode) -> ListNode:
        temp = ans = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                ans.next = l1
                l1 = l1.next
            else:
                ans.next = l2
                l2 = l2.next
            ans = ans.next
        ans.next = l1 or l2 
        return temp.next
# Runtime: 36 ms, faster than 70.49% of Python3 online submissions for Merge Two Sorted Lists.
# Memory Usage: 14 MB, less than 6.61% of Python3 online submissions for Merge Two Sorted Lists.

変わった点としてはwhile文の条件がorからandに変わっている点と、その変更に伴って

ans.next = l1 or l2

が追加されている点です。
こうすることによって冗長な部分を大幅に削れました。
l1とl2の両方が存在している間は比較を、もし片方しか存在しない場合はそのままの順番で残りを代入してくれます。

良さげな解答があれば追記します。