(* •̀ᴗ-)✧
嗨，我是wec，今天是Day 4。

🔎 題目難度與描述

難度：EASY

題目描述：

給定兩個已經按升序排列的鏈結串列l1 和l2，將這兩個串列合併成一個新的排序鏈結串列，並返回這個新的鏈結串列。新的鏈結串列應該要是按升序排列。

🔎 解題思路＆程式碼

1️⃣ 遞迴法

第1步： 從頭開始比較，每次比較串列的第一個節點，看哪個小。
第2步： 把小的那個節點放進新串列裡，然後那個串列就往下一個節點移動。
第3步： 繼續比較，直到其中一個串列為空，並把另一個還沒走完的串列剩下的部分接到新的串列後。
程式碼：

def merge_two_lists(l1, l2)
  return l1 || l2 if l1.nil? || l2.nil?
  
  if l1.val < l2.val
    l1.next = merge_two_lists(l1.next, l2)
    l1
  else
    l2.next = merge_two_lists(l1, l2.next)
    l2
  end
end

2️⃣ 迭代法

第1步： 準備一個空的列表（用來放合併結果）。
第2步： 一個指針指向l1、另一個指針指向l2
第3步： 兩個指針所指的數字作比較，比較小的放在列表裡。
第4步： 比較到有其中一個列表為空（數字都放進空列表裡了）。
第5步： 另一個列表剩下的數字直接全放進空列表裡。
程式碼：

def merge_sorted_lists(l1, l2)
  merged_list = []
  i, j = 0, 0

  while i < l1.length && j < l2.length
    if l1[i] <= l2[j]
      merged_list << l1[i]
      i += 1
    else
      merged_list << l2[j]
      j += 1
    end
  end

  merged_list.concat(l1[i..-1]).concat(l2[j..-1])
  merged_list
end

🔎 總結

時間複雜度比較

遞迴法： 時間複雜度為O(n+m)
迭代法： 時間複雜度為O(n+m)
➡️ 兩者一樣！不過迭代法在去除掉存放結果的列表的空間複雜度為O(1)。遞迴法在每次動作都得紀錄當前列表的狀態，但迭代法不用，所以在處理較多數據的情況下，迭代法比遞迴法更勝一籌٩(•̤̀ᵕ•̤́๑)。

那麼，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃家常起司口味的奇多。
明天要說：Ruby精選刷題！練等要先從easy開始III(>∀･)⌒☆