合併兩個已排序的列表

Algorithem_MergeTwoSortedLists#

給定兩個已排序的鏈結串列 list1 和 list2 的頭節點。

將這兩個串列合併為一個已排序的串列。合併後的串列應由第一個兩個串列的節點拼接而成。

返回合併後的鏈結串列的頭節點。

示例 1：

輸入：list1 = [1,2,4]，list2 = [1,3,4]
輸出：[1,1,2,3,4,4]

示例 2：

輸入：list1 = []，list2 = []
輸出：[]

示例 3：

輸入：list1 = []，list2 = [0]
輸出：[0]

解法#

需求是合併兩個有序的鏈結串列，所以解法是

判斷 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
        }
    }
}