解题步骤
- 新建一个新链表,作为返回结果
- 用指针遍历两个有序链表,并比较两个链表的当前节点,较小者先接入新链表,并将指针后移一步
- 链表遍历结束,返回新链表
通过链表的方式实现
- 时间复杂度:O (m + n)
空间复杂度:O (1)
function mergeTwoLists(list1, list2) {
const res = new ListNode(0);
let p = res;
let p1 = list1;
let p2 = list2;
while (p1 && p2) {
if (p1.val < p2.val) {
p.next = p1;
p1 = p1.next;
} else {
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
if (p1) {
p.next = p1;
}
if (p2) {
p.next = p2;
}
return res.next;
}
代码中主要遍历了 list1 和 list2 ,所以时间复杂度是 O (m + n),而空间复杂度是 O (1),因为我们新建的变量都是一些指针,不是数组也不是矩阵,所以是不会随着数据增大而增大。