题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 均按 非递减顺序 排列
代码及注释
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
// 创建一个虚拟头节点作为合并后的链表的起始节点
dummy := &ListNode{}
// 创建一个指针 cur 指向当前合并后的链表的末尾
cur := dummy
// 遍历两个链表,比较当前节点的值,将较小的节点加入到合并后的链表中
for list1 != nil && list2 != nil {
if list1.Val > list2.Val {
// 如果 list1 的当前节点的值大于 list2 的当前节点的值
// 将 list2 的当前节点加入到合并后的链表中
cur.Next = list2
list2 = list2.Next // 移动 list2 的指针
} else {
// 否则,将 list1 的当前节点加入到合并后的链表中
cur.Next = list1
list1 = list1.Next // 移动 list1 的指针
}
cur = cur.Next // 移动 cur 指针到下一个位置
}
// 某一个链表已经遍历完,将另一个链表的剩余部分加入到合并后的链表的末尾
if list1 == nil {
cur.Next = list2
} else {
cur.Next = list1
}
// 返回合并后的链表,从虚拟头节点的下一个节点开始
return dummy.Next
}
这个算法的时间复杂度是 O(n + m),其中 n 和 m 分别是两个链表的长度,因为我们需要遍历两个链表一次。