网站建设策略书,品牌seo主要做什么,建设网站江西,外贸seo网站推广合并两个有序链表
https://leetcode.cn/problems/merge-two-sorted-lists/
描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1 输入#xff1a;l1 [1,2,4], l2 [1,3,4]
输出#xff1a;[1,1,2,3,4,4]示例 …合并两个有序链表
https://leetcode.cn/problems/merge-two-sorted-lists/
描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 100l1 和 l2 均按 非递减顺序 排列
算法实现
1 遍历两个链表依次比较存入结果链表
/*** Definition for singly-linked list.* class ListNode {* val: number* next: ListNode | null* constructor(val?: number, next?: ListNode | null) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }* }*/function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {const res new ListNode();let p res; // 用于遍历 res 的指针let p1 list1; // 用于遍历 list1 的指针不影响原 list1let p2 list2; // 用于遍历 list2 的指针不影响原 list2// 遍历两个链表并接入值有序的接入// 遍历链表必须有指针不停的执行 指针指针.nextwhile(p1 p2) {if(p1.val p2.val) {p.next p1; // 结果链表添加最小元素p1 p1.next; // p1这个链表后移一位} else {p.next p2; // 结果链表添加最小元素p2 p2.next; // 后移}p p.next; // 结果链表 后移}// 接着考虑 p1或p2 其中一个空一个不空的情况p1 (p.next p1);p2 (p.next p2);return res.next;
};解题思路 与归并排序中合并两个有序数组很相似将数组替换成链表即可 解题步骤 新建一个新链表作为返回结果用指针遍历两个有序链表并比较两个链表的当前节点较小者先接入新链表并将指针后移一步链表遍历结束返回新链表 时间复杂度O(n) O(mn) 空间复杂度O(1) 新建链表是一个指针存储的是常量
2 基于递归
/*** Definition for singly-linked list.* class ListNode {* val: number* next: ListNode | null* constructor(val?: number, next?: ListNode | null) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }* }*/function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {if (!list1) return list2;if (!list2) return list1;// list1 大于 list2的值if (list1.val list2.val) {list1.next mergeTwoLists(list1.next, list2);return list1;}// list1 小于等于 list2的值list2.next mergeTwoLists(list1, list2.next);return list2;
};这个思路就是递归比较和合并没啥要说的时间复杂度O(n) O(mn) 空间复杂度O(n) 使用了 mn 个调用栈O(mn)
