アルゴリズム_2つのソートされたリストをマージする

Algorithem_MergeTwoSortedLists#

与えられたのは、2 つのソートされたリンクリスト list1 と list2 のヘッドです。

2 つのリストを 1 つのソートされたリストにマージします。このリストは、最初の 2 つのリストのノードをつなぎ合わせて作成されるべきです。

マージされたリンクリストのヘッドを返します。

例 1:

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

例 2:

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

例 3:

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

解法#

要求は 2 つの有序 LinkList をマージすることなので、解法は

list1.val と list2.val の大小を判断する。
list1.val が list2.val 以下であれば、最初の要素は list1.val で、その後 list1.next と list2 を再帰的に比較します —— つまり、list1.next.val と list2.val の大小を比較します。
list1.val が list2.val より大きければ、最初の要素は list2.val で、その後 list1 と list2.next を再帰的に比較します —— つまり、list1.val と list2.next.val の大小を比較します。
list1 が空であれば list2 を返し、list2 が空であれば list1 を返します。

コードは以下の通りです：


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? { 
        if list1 == nil {
            return list2
        }
        
        if list2 == nil {
            return list1
        }
        
        if list1!.val <= list2!.val {
            list1?.next = mergeTwoLists(list1?.next, list2)
            return list1
        }
        else {
            list2?.next = mergeTwoLists(list1, list2?.next)
            return list2
        }
    }
}