21. Merge Two Sorted Lists

2つのソート済み連結リスト list1 と list2 の先頭ノードが与えられます。

この2つのリストを1つのソート済みリストにマージしてください。マージは、最初の2つのリストのノードをつなぎ合わせて行います。

マージされた連結リストの先頭ノードを返してください。

例 1:
入力: list1 = [1,2,4], list2 = [1,3,4]
出力: [1,1,2,3,4,4]

例 2:
入力: list1 = [], list2 = []
出力: []

例 3:
入力: list1 = [], list2 = [0]
出力: [0]

・リストのいずれかが null の場合

list1 が null なら、list2 を返す。
list2 が null なら、list1 を返す。

・再帰的な比較と結合
list1.val が list2.val より小さい場合、list1 を head に設定し、head.next に再帰的に list1.next と list2 を結合する。
逆に、list2.val が小さい場合も同様。