59.合并两个有序链表
题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例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 均按 非递减顺序 排列
思路
循环遍历比较哪个节点大就添加，遍历到一个链表结束后，把剩下的链表都拼接上就可以了(因为每个链表都已经是有序的)
class Solution {
fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
if (list1 == null) {
return list2
}
if (list2 == null) {
return list1
}
var list1Node = list1
var list2Node = list2
var result: ListNode? = null
var current: ListNode? = null
while (list1Node != null && list2Node != null) {
if (list1Node.`val` < list2Node.`val`) {
if (result == null) {
// 没初始化根节点
result = list1Node
current = list1Node
// list1Node继续走
list1Node = list1Node.next
continue
}
// 初始化根节点了
current?.next = list1Node
list1Node = list1Node.next
} else {
if (result == null) {
result = list2Node
current = list2Node
list2Node = list2Node.next
continue
}
current?.next = list2Node
list2Node = list2Node.next
}
// 更新当前的链表位置
current = current?.next
}
// 最后遍历完后，最多有一个链表有剩余，直接拼接上就好，因为这两个链表都已经是有序的了
current?.next = list1Node ?: list2Node
return result
}
class ListNode(var `val`: Int) {
var value: Int = 0
var next: ListNode? = null
}
}
上面可以看到有一部分代码都是为了判断result是不是null单独处理的，其实可以不用这样。
可以默认把result = ListNode(0) // 什么值都可以。然后最后return的时候返回result.next 就可以了，这样就不用判断result是不是赋值了，可以让代码更简洁。
复杂度
- 时间复杂度: O(m + n)，每个节点恰好被访问一次
- 空间复杂度: O(1)，仅移动指针，不创建新节点
- 邮箱 ：charon.chui@gmail.com
- Good Luck!