21. 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.

 

Example 1:


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

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

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

Constraints:

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.

---

Code

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}

	merged_list := &ListNode{Val: -1, Next: nil}
	merged_list_head := merged_list

	for list1 != nil && list2 != nil {
		if list1.Val < list2.Val {
			merged_list_head.Next = list1 
			list1 = list1.Next 
		} else {
			merged_list_head.Next = list2
			list2 = list2.Next
		}
		fmt.Println("::", merged_list_head.Val)
		merged_list_head = merged_list_head.Next
	}

	if list1 != nil {
		merged_list_head.Next = list1
	}
	if list2 != nil {
		merged_list_head.Next = list2
	}

	return merged_list.Next
}

 

시간 복잡도 분석

1. 초기 조건 확인:
   • 함수는 먼저 list1 또는 list2가 nil인지 확인합니다. 이는 상수 시간 O(1)이 소요됩니다.
2. 주 반복문:
   • 주 반복문은 list1과 list2의 모든 노드를 순회합니다. 두 리스트의 길이를 각각 n과 m이라고 하면, 반복문은 두 리스트의 길이 합인 n + m만큼 실행됩니다. 각 반복문 내의 연산은 상수 시간 O(1)이므로 주 반복문의 시간 복잡도는 O(n + m)입니다.
3. 잔여 노드 연결:
   • 반복문이 종료된 후, 아직 남아 있는 노드를 연결합니다. 이는 최대 n 또는 m만큼 실행될 수 있으므로, 이 부분의 시간 복잡도도 O(n + m)입니다.

따라서, 전체 함수의 시간 복잡도는 O(n + m)입니다. 여기서 n은 list1의 길이이고, m은 list2의 길이입니다.