21. 合并两个有序链表

🟢   🔖  递归 链表  🔗 力扣 LeetCode

题目

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]

Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []

Output: []

Example 3:

Input: list1 = [], list2 = [0]

Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

题目大意

合并 2 个有序链表

解题思路

利用归并排序的思想，具体步骤如下：

• 使用哑节点 newHead 构造一个头节点，并使用 prev 指向 newHead 用于遍历；
• 然后判断 list1 和 list2 头节点的值，将较小的头节点加入到合并后的链表中，并向后移动该链表的头节点指针；
• 重复上一步操作，直到两个链表中出现链表为空的情况；
• 将剩余链表链接到合并后的链表中；
• 返回合并后有序链表的头节点 newHead.next。

复杂度分析

• 时间复杂度：O(m + n)，其中 m、n 分别为 list1 和 list2 的长度，需要对每个节点遍历一次。
• 空间复杂度：O(1)，链表是原地修改的，没有占用额外的空间用于存储节点，只使用了常量级别的变量。

代码

/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
	const newHead = new ListNode();
	let prev = newHead;

	while (list1 && list2) {
		if (list1.val < list2.val) {
			prev.next = list1;
			list1 = list1.next;
		} else {
			prev.next = list2;
			list2 = list2.next;
		}
		prev = prev.next;
	}

	prev.next = list1 != null ? list1 : list2;
	return newHead.next;
};

相关题目

题号	标题	题解	标签	难度
23	合并 K 个升序链表	[✓]	链表 分治 堆（优先队列） 1+
88	合并两个有序数组	[✓]	数组 双指针 排序
148	排序链表	[✓]	链表 双指针 分治 2+
244	最短单词距离 II 🔒		设计 数组 哈希表 2+
1634	求两个多项式链表的和 🔒		链表 数学 双指针
1940	排序数组之间的最长公共子序列 🔒		数组 哈希表 计数
2570	合并两个二维数组 - 求和法		数组 哈希表 双指针