21. 合并两个有序链表,22. 括号生成,23. 合并 K 个升序链表,每题做详细思路梳理,配套Python&Java双语代码, 2024.03.13 可通过leetcode所有测试用例。
目录
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
均按 非递减顺序 排列
解题思路
要合并两个升序链表为一个新的升序链表,我们可以使用一个指针追踪两个链表的当前节点,并比较它们的值以决定哪一个节点应该先被加入到新链表中。一旦我们选中一个节点,我们就将其添加到新链表的末尾,并移动对应链表的指针到下一个节点。重复这个过程直到所有节点都被检查过。
解题思路如下:
- 创建一个哨兵(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 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 = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
# 将非空链表的剩余部分接在新链表的末尾
current.next = list1 if list1 else list2
# 哨兵节点的下一个节点即为合并后链表的头节点
return dummy.next
22. 括号生成
数字
n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。示例 1:
输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"]示例 2:
输入:n = 1 输出:["()"]提示:
1 <= n <= 8
解题思路
这个问题是一个经典的回溯算法问题,关键在于如何确保在任何时刻插入的括号序列都是有效的。
解题思路如下:
- 初始化:结果集合
res
用于存储所有有效的括号组合。 - 递归函数:定义一个递归函数
generate
,它接受当前的括号字符串current
,以及两个计数器open
和close
分别表示已放置的左括号和右括号数量。 - 递归终止条件:当
current
字符串长度达到 2 * n 时,表示形成了一个完整的括号组合,将其添加到结果集res
中,并返回。 - 递归逻辑:
- 如果
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)
return
if 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 = [[]] 输出:[]
解题思路
这个问题的关键在于如何有效地合并多个已排序的链表。一种方法是使用最小堆(优先队列)来保持跟踪每个链表的当前最小节点,从而以线性时间复杂度合并链表。这个解决方案的基本步骤如下:
初始化最小堆:首先,创建一个最小堆,用于存储每个链表的当前最小节点。堆中的每个元素都是一个节点及其来源链表的索引。
填充堆:遍历链表数组,将每个链表的头节点插入到最小堆中。这样,堆中始终保持有每个链表当前的最小节点。
合并链表:创建一个虚拟头节点
dummy
,以及一个指向当前合并链表末尾的指针tail
。然后,不断从最小堆中取出最小节点,添加到tail
的后面,并将该节点的下一个节点(如果存在)插入到最小堆中。重复这个过程,直到堆为空。返回结果:返回
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 = dummy
pq = 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 = node
current = current.next
if node.next:
pq.put((node.next.val, i, node.next))
return dummy.next