LeetCode 21. Merge Two Sorted Lists

はじめに

LeetCode 「21. Merge Two Sorted Lists」の問題をGoで解きました。

問題

https://leetcode.com/problems/merge-two-sorted-lists/description/

問題文

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

和訳
2つのソート済み連結リストlist1とlist2の先頭が与えられている。

この2つのリストを1つのソート済みリストに結合しなさい。このリストは、最初の2つのリストのノードをつなぎ合わせたものでなければならない。

マージされた連結リストの先頭を返せ。

例

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

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

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

制約

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

解答

list1 と list2 を繋げて新たなリストを構築する問題です。

仮の先頭ノードdummyを作成し、そこからcurrentを使ってリストを構築します。
dummy ノードを使うことで、最初のノードだけ特別扱いせずに済むため、実装が簡潔になります。

それぞれを先頭から比較して小さい方をcurrent.Nextにして進めます。
ループを抜けた後、どちらかのリストが残っていたらそのまま繋げます。
list1 や list2 のどちらかが nil の場合でも、そのまま接続されるため特別な処理は不要です。

最後に dummy.Next を返せば新しいリストの先頭になります。

コード

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	dummy := &ListNode{} // 仮の先頭ノード
	current := dummy

	for list1 != nil && list2 != nil {
		if list1.Val <= list2.Val {
			current.Next = list1
			list1 = list1.Next
		} else {
			current.Next = list2
			list2 = list2.Next
		}
		current = current.Next
	}

	// 残っている方を繋げる
	if list1 != nil {
		current.Next = list1
	} else {
		current.Next = list2
	}
    
	return dummy.Next
}

計算量

• 時間的計算量：O(n + m)
  • nとmはそれぞれlist1とlist2のノード数
• 空間的計算量：O(1)