21. Merge Two Sorted Lists

🟢   🔖  递归 链表  🔗 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。

代码

/**
 * @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 个升序链表
• 88. 合并两个有序数组
• 148. 排序链表
• 🔒 Shortest Word Distance II
• 🔒 Add Two Polynomials Represented as Linked Lists
• 🔒 Longest Common Subsequence Between Sorted Arrays
• 2570. 合并两个二维数组 - 求和法

- [23. 合并 K 个升序链表](./0023.md)
- [88. 合并两个有序数组](./0088.md)
- [148. 排序链表](https://leetcode.com/problems/sort-list)
- [🔒 Shortest Word Distance II](https://leetcode.com/problems/shortest-word-distance-ii)
- [🔒 Add Two Polynomials Represented as Linked Lists](https://leetcode.com/problems/add-two-polynomials-represented-as-linked-lists)
- [🔒 Longest Common Subsequence Between Sorted Arrays](https://leetcode.com/problems/longest-common-subsequence-between-sorted-arrays)
- [2570. 合并两个二维数组 - 求和法](https://leetcode.com/problems/merge-two-2d-arrays-by-summing-values)