LeetCode 021 Merge Two Sorted Lists

LeetCode

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

Merge the two lists in a 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.

题目大意：

合并两个LL

解题思路：

N/A

解题步骤：

N/A

注意事项：

1. Fake Node的引入

Python代码：

def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
	fake_head = ListNode(0)
	it, it2, it_res = list1, list2, fake_head
	while it and it2:
		if it.val <= it2.val:
			it_res.next = it
			it = it.next
			it_res = it_res.next
		else:
			it_res.next = it2
			it2 = it2.next
			it_res = it_res.next
	if it:
		it_res.next = it
	if it2:
		it_res.next = it2
	return fake_head.next

算法分析：

时间复杂度为O(n + m)，空间复杂度O(1)