21. 合并两个有序链表

题目描述：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4] 
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = [] 
输出：[]

示例 3：

输入：l1 = [], l2 = [0] 
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

---

解题分析及思路：

方法：迭代

思路：

我们可以用迭代的方法实现上述算法。

建立一个 头节点 root，用于保存合并的链表的开始处。我们需要维护一个指针 pre，指向当前已经合并的链表的最后一个节点。

然后我们比较两个链表的头节点，将值较小的节点加入到合并链表中，并将对应链表的指针后移一位。当其中一个链表的指针为空时，我们将另一个链表的剩余部分加入到合并链表的最后。

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	var root = &ListNode{Val: -101}
	var pre = root
	for list1 != nil && list2 != nil {
		if list1.Val <= list2.Val {
			pre.Next = list1
			list1 = list1.Next
		} else {
			pre.Next = list2
			list2 = list2.Next
		}
		pre = pre.Next
	}
	if list1 != nil {
		pre.Next = list1
	}
	if list2 != nil {
		pre.Next = list2
	}
	return root.Next
}

复杂度：

• 时间复杂度：O(N)，其中 N 是链表的节点数量。
• 空间复杂度：O(1)，只使用常数额外空间。

执行结果：

• 执行耗时:2 ms,击败了36.99% 的Go用户
• 内存消耗:2.3 MB,击败了46.62% 的Go用户