力扣 21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
方案一：遍历双链表，通过过滤器实现要求。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
// 定义哨兵节点
dummy := &ListNode{}
pre := dummy
// 在两个链表都不为空的前提下
for list1 != nil && list2 != nil {
// 定义 next 节点
var next *ListNode
// 过滤器，过滤出 next 节点
// 如果 list1 小 next 就是 list1，否则为 list2
// 被选中的节点需要滑动到自己的 next 指针上
if list1.Val < list2.Val {
next = list1
list1 = list1.Next
} else {
next = list2
list2 = list2.Next
}
// 为 pre 节点赋值 next 节点
pre.Next = next
// 将 pre 节点前进到 next 指针处
pre = pre.Next
}
// 如果 list1 不为空，就将 next 拼接到 list1 之后
if list1 != nil {
pre.Next = list1
}
// 如果 list2 不为空，就将 next 拼接到 list2 之后
if list2 != nil {
pre.Next = list2
}
// 返回哨兵节点的 next 指针
return dummy.Next
}
- 时间复杂度：O(n)，因为最多需要遍历两个链表的所有节点，所以时间复杂度为 O(n)。
- 空间复杂度：O(1)，因为使用了常数级别的辅助变量，所以空间复杂度为 O(1)。