【LeetCode】21. Merge Two Sorted Lists

問題へのリンク

問題概要

ソートされた２つの連結リストを統合して，ソートされた連結リストを返す．

例：

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

制約

• 各リストのノードの数$[0,50]$
• $-100 \leq Node.val \leq 100$
• l1，l2はどちらも昇順にソートされている

考えたこと

1. l1，l2の先頭から$Node.val$を比較して小さい方を$res$に結合
2. 結合した方のノードを一つ進める
3. 一方がnullになるまで①→②を繰り返す
4. nullでない方をresに結合

という手順でいけそう．

例を利用すると，

l1 = [1,2,4]
l2 = [1,3,4]
res = []

同じ値なのでl1を採用

l1 = [2,4]
l2 = [1,3,4]
res = [1]

$l2.val(=1) < l1.val(=2)$よりl2を採用

l1 = [2,4]
l2 = [3,4]
res = [1,1]

$l1.val(=2) < l2.val(=3)$よりl1を採用

l1 = [4]
l2 = [3,4]
res = [1,1,2]

$l2.val(=3) < l1.val(=4)$よりl2を採用

l1 = [4]
l2 = [4]
res = [1,1,2,3]

同じ値なのでl1を採用

l1 = []
l2 = [4]
res = [1,1,2,3,4]

l1 == nullなので，l2以下を全てresに結合

l1 = []
l2 = []
res = [1,1,2,3,4,4]

このように所望の結果が得られる．

# 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, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = res = ListNode()
        
        while l1 and l2:
            if l1.val <= l2.val:
                dummy.next = l1
                l1 = l1.next
            else:
                dummy.next = l2
                l2 = l2.next
            
            dummy = dummy.next
            
        dummy.next = l1 or l2
            
        return res.next

Tips

下から2行目の

dummy.next = l1 or l2

はステップ４．に相当し，

• まずl1を評価してl1 == Noneの時はl2を返す．
• l1 != Noneの時はl1を返す．

という処理が行われます^[1]．

脚注

1. 6.11. ブール演算 (boolean operation)｜Python 3.9.2 ドキュメント