21. 合并两个有序链表，22. 括号生成，23. 合并 K 个升序链表，每题做详细思路梳理，配套Python&Java双语代码， 2024.03.13 可通过leetcode所有测试用例。

目录

21. 合并两个有序链表

解题思路

完整代码

Java

Python

22. 括号生成

解题思路

完整代码

Java

Python

23. 合并 K 个升序链表

解题思路

完整代码

Java

Python

---

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 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. 创建一个哨兵（dummy）节点，它将作为新链表的起始节点，这样可以简化插入逻辑并最终返回合并后的链表。
2. 维持一个当前节点指针，初始指向哨兵节点。
3. 在两个链表都非空的情况下，比较两个链表当前节点的值。将较小值的节点接在当前节点之后，并将该链表的指针后移。
4. 如果一个链表变为空，直接将另一个链表的剩余部分接在当前链表之后。
5. 最终，哨兵节点的下一个节点即为合并后链表的头节点。

完整代码

Java

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
public class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {// 创建哨兵节点ListNode dummy = new ListNode(-1);// 当前节点指针初始化指向哨兵节点ListNode current = dummy;// 遍历两个链表，直到至少一个链表为空while (l1 != null && l2 != null) {// 比较两个链表当前节点的值，选择较小者加入到新链表中if (l1.val < l2.val) {current.next = l1;l1 = l1.next;} else {current.next = l2;l2 = l2.next;}current = current.next;}// 将非空链表的剩余部分接在新链表的末尾current.next = l1 != null ? l1 : l2;// 哨兵节点的下一个节点即为合并后链表的头节点return dummy.next;}
}

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:# 创建哨兵节点dummy = ListNode(-1)# 当前节点指针初始化指向哨兵节点current = dummy# 遍历两个链表，直到至少一个链表为空while list1 and list2:# 比较两个链表当前节点的值，选择较小者加入到新链表中if list1.val < list2.val:current.next = list1list1 = list1.nextelse:current.next = list2list2 = list2.nextcurrent = current.next# 将非空链表的剩余部分接在新链表的末尾current.next = list1 if list1 else list2# 哨兵节点的下一个节点即为合并后链表的头节点return dummy.next

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

解题思路

这个问题是一个经典的回溯算法问题，关键在于如何确保在任何时刻插入的括号序列都是有效的。

解题思路如下：

1. 初始化：结果集合 res 用于存储所有有效的括号组合。
2. 递归函数：定义一个递归函数 generate，它接受当前的括号字符串 current，以及两个计数器 open 和 close 分别表示已放置的左括号和右括号数量。
3. 递归终止条件：当 current 字符串长度达到 2 * n 时，表示形成了一个完整的括号组合，将其添加到结果集 res 中，并返回。
4. 递归逻辑：
   • 如果 open 小于 n，可以添加一个左括号，并递归调用 generate。
   • 如果 close 小于 open，可以添加一个右括号，并递归调用 generate。

完整代码

Java

public class Solution {public List<String> generateParenthesis(int n) {List<String> res = new ArrayList<>();backtrack(res, "", 0, 0, n);return res;}private void backtrack(List<String> res, String current, int open, int close, int max) {if (current.length() == max * 2) {res.add(current);return;}if (open < max) {backtrack(res, current + "(", open + 1, close, max);}if (close < open) {backtrack(res, current + ")", open, close + 1, max);}}public static void main(String[] args) {Solution solution = new Solution();List<String> result = solution.generateParenthesis(3);System.out.println(result);}
}

Python

class Solution:def generateParenthesis(self, n: int) -> List[str]:def backtrack(s='', left=0, right=0):if len(s) == 2 * n:res.append(s)returnif left < n:backtrack(s+'(', left+1, right)if right < left:backtrack(s+')', left, right+1)res = []backtrack()return res

23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[1->4->5,1->3->4,2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

解题思路

        这个问题的关键在于如何有效地合并多个已排序的链表。一种方法是使用最小堆（优先队列）来保持跟踪每个链表的当前最小节点，从而以线性时间复杂度合并链表。这个解决方案的基本步骤如下：

1. 初始化最小堆：首先，创建一个最小堆，用于存储每个链表的当前最小节点。堆中的每个元素都是一个节点及其来源链表的索引。

2. 填充堆：遍历链表数组，将每个链表的头节点插入到最小堆中。这样，堆中始终保持有每个链表当前的最小节点。

3. 合并链表：创建一个虚拟头节点 dummy，以及一个指向当前合并链表末尾的指针 tail。然后，不断从最小堆中取出最小节点，添加到 tail 的后面，并将该节点的下一个节点（如果存在）插入到最小堆中。重复这个过程，直到堆为空。

4. 返回结果：返回 dummy 的下一个节点，即合并后链表的头节点。

完整代码

Java

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/public class Solution {public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0) return null;PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);for (ListNode list : lists) {if (list != null) {pq.add(list);}}ListNode dummy = new ListNode(0);ListNode tail = dummy;while (!pq.isEmpty()) {tail.next = pq.poll();tail = tail.next;if (tail.next != null) {pq.add(tail.next);}}return dummy.next;}
}

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from queue import PriorityQueue
class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:dummy = ListNode()current = dummypq = PriorityQueue()for i, node in enumerate(lists):if node:pq.put((node.val, i, node))while not pq.empty():val, i, node = pq.get()current.next = nodecurrent = current.nextif node.next:pq.put((node.next.val, i, node.next))return dummy.next