题目描述#

给你两个按升序排列的链表 list1 和 list2，要求把它们合并成一个新的升序链表并返回。

这里的“合并”不是重新创建所有节点，而是把两个链表中原有的节点按顺序接起来，最终得到一条有序的新链表。

思路#

这份代码使用了一个很常见的链表技巧：先创建一个哑节点 dummy，再用 cur 指针始终指向新链表的尾部。这样在拼接节点时就不用单独处理头节点，代码会简单很多。

接下来同时遍历 list1 和 list2。每次比较两个链表当前节点的值，谁更小，就把谁接到 cur.Next 后面，并把对应链表向后移动一位。然后再让 cur 也往后走一步，表示新链表已经多接上了一个节点。

当其中一个链表先走完之后，另一个链表剩下的部分一定已经是有序的，而且其中所有节点都不需要再比较了，直接整体挂到 cur.Next 后面即可。

因为每个节点只会被访问一次，所以时间复杂度是 O(m+n)，其中 m 和 n 分别是两个链表的长度。额外只用了几个指针变量，空间复杂度是 O(1)。

代码#

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	dummy := &ListNode{}
	cur := dummy

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

	if list1 != nil {
		cur.Next = list1
	}
	if list2 != nil {
		cur.Next = list2
	}
	return dummy.Next
}