数据结构与算法之排序: Leetcode 21. 合并两个有序链表 (Typescript版)

合并两个有序链表

• 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 <= 100
• l1 和 l2 均按 非递减顺序 排列

算法实现

1 ）遍历两个链表，依次比较存入结果链表

/*** Definition for singly-linked list.* class ListNode {*     val: number*     next: ListNode | null*     constructor(val?: number, next?: ListNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.next = (next===undefined ? 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(m+n)
• 空间复杂度：O(1)
  • 新建链表是一个指针，存储的是常量

2 ）基于递归

/*** Definition for singly-linked list.* class ListNode {*     val: number*     next: ListNode | null*     constructor(val?: number, next?: ListNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.next = (next===undefined ? 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(m+n)
• 空间复杂度：O(n)
  • 使用了 m+n 个调用栈
  • O(m+n)