1. 合并两个有序链表
题⽬描述
将两个升序链表合并为⼀个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输⼊：1->2->4, 1->3->4 输出：1->1->2->3->4->4
前置知识
递归 链表
思路
本题可以使⽤递归来解，将两个链表头部较⼩的⼀个与剩下的元素合并，并返回排好序的链表 头，当两条链表中的⼀条为空时终⽌递归。 关键点 掌握链表数据结构 考虑边界情况
代码
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
const mergeTwoLists = function (l1, l2) {
if (l1 === null) {
return l2;
}
if (l2 === null) {
return l1;
}
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};复杂度分析
M、N 是两条链表 l1、l2 的⻓度 时间复杂度： 空间复杂度： 扩展 你可以使⽤迭代的⽅式求解么？ 迭代的 CPP 代码如下：
扩展
你可以使⽤迭代的⽅式求解么？
迭代的 JS 代码如下：
var mergeTwoLists = function (l1, l2) {
const prehead = new ListNode(-1);
let prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
prev.next = l1 === null ? l2 : l1;
return prehead.next;
};2. 括号⽣成
题⽬描述
数字 n 代表⽣成括号的对数，请你设计⼀个函数，⽤于能够⽣成所有可能的并且 有效的 括号组合。 示例： 输⼊：n = 3 输出：[ "((()))", "(()())", "(())()","()(())",
前置知识
DFS 回溯法
思路
本题是 有效括号 的升级版。 由于我们需要求解所有的可能， 因此回溯就不难想到。回溯的思路和写法相对⽐较固定，并且 回溯的优化⼿段⼤多是剪枝。 不难想到， 如果左括号的数⽬⼩于右括号，我们可以提前退出，这就是这道题的剪枝。 ⽐如 ()).... ，后⾯就不⽤看了，直接退出即可。回溯的退出条件也不难想到，那就是： 左括号数⽬等于右括号数⽬ 左括号数⽬ + 右括号数⽬ = 2 * n 由于我们需要剪枝， 因此必须从左开始遍历。（WHY？） 因此这道题我们可以使⽤深度优先搜索(回溯思想)，从空字符串开始构造，做加法， 即 dfs(左 括号数, 右括号数⽬, 路径)， 我们从 dfs(0, 0, '') 开始。
伪代码：
res = []
def dfs(l, r, s):
if l > n or r > n: return
if (l == r == n): res.append(s)
# 剪枝，提⾼算法效率
if l < r: return
# 加⼀个左括号
dfs(l + 1, r, s + '(')
# 加⼀个右括号
dfs(l, r + 1, s + ')')
dfs(0, 0, '')
return res由于字符串的不可变性， 因此我们⽆需 撤销 s 的选择 。但是当你使⽤ C++ 等语⾔的时候， 就
需要注意撤销 s 的选择了。类似：
s.push_back(')');
dfs(l, r + 1, s);
s.pop_back();关键点
当 l < r 时记得剪枝
代码
/**
* @param {number} n
* @return {string[]}
* @param l 左括号已经⽤了⼏个
* @param r 右括号已经⽤了⼏个
* @param str 当前递归得到的拼接字符串结果
* @param res 结果集
*/
const generateParenthesis = function (n) {
const res = [];
function dfs(l, r, str) {
if (l == n && r == n) {
return res.push(str);
}
// l ⼩于 r 时不满⾜条件 剪枝
if (l < r) {
return;
}
// l ⼩于 n 时可以插⼊左括号，最多可以插⼊ n 个
if (l < n) {
dfs(l + 1, r, str + "(");
}
// r < l 时 可以插⼊右括号
if (r < l) {
dfs(l, r + 1, str + ")");
}
}
dfs(0, 0, "");
return res;
};复杂度分析
时间复杂度：O(2^N) 空间复杂度：O(2^N)
3. 合并 K 个排序链表
题⽬描述
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输⼊: [ 1->4->5, 1->3->4, 2->6 ]
输出: 1->1->2->3->4->4->5->6
前置知识
链表
归并排序
思路
这道题⽬是合并 k 个已排序的链表，号称 leetcode ⽬前 最难 的链表题。 和之前我们解决的 88.merge-sorted-array很像。 他们有两点区别：
- 这道题的数据结构是链表，那道是数组。这个其实不复杂，毕竟都是线性的数据结构。
- 这道题需要合并 k 个元素，那道则只需要合并两个。这个是两题的关键差别，也是这道题难度为 hard 的原因。
因此我们可以看出，这道题⽬是 88.merge-sorted-array 的进阶版本。其实思路也有点像，我 们来具体分析下第⼆条。 如果你熟悉合并排序的话，你会发现它就是 合并排序的⼀部分 。 具体我们可以来看⼀个动画。
关键点解析
分治
归并排序(merge sort)
代码
/*
* @lc app=leetcode id=23 lang=javascript
*
* [23] Merge k Sorted Lists
*
* https://leetcode.com/problems/merge-k-sorted-lists/description/
*
*/
function mergeTwoLists(l1, l2) {
const dummyHead = {};
let current = dummyHead;
// l1: 1 -> 3 -> 5
// l2: 2 -> 4 -> 6
while (l1 !== null && l2 !== null) {
if (l1.val < l2.val) {
current.next = l1; // 把⼩的添加到结果链表
current = current.next; // 移动结果链表的指针
l1 = l1.next; // 移动⼩的那个链表的指针
} else {
current.next = l2;
current = current.next;
l2 = l2.next;
}
}
if (l1 === null) {
current.next = l2;
} else {
current.next = l1;
}
return dummyHead.next;
}
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function (lists) {
// 图参考： https://zhuanlan.zhihu.com/p/61796021
if (lists.length === 0) return null;
if (lists.length === 1) return lists[0];
if (lists.length === 2) {
return mergeTwoLists(lists[0], lists[1]);
}
const mid = lists.length >> 1;
const l1 = [];
for (let i = 0; i < mid; i++) {
l1[i] = lists[i];
}
const l2 = [];
for (let i = mid, j = 0; i < lists.length; i++, j++) {
l2[j] = lists[i];
}
return mergeTwoLists(mergeKLists(l1), mergeKLists(l2));
};
复杂度分析
时间复杂度：O(k*n*logk)
空间复杂度：O(logk)
相关题⽬ 88.merge-sorted-array
扩展
这道题其实可以⽤堆来做，感兴趣的同学尝试⼀下吧。
4. 两两交换链表中的节点
题⽬描述
给定⼀个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，⽽是需要实际的进⾏节点交换。
示例 1：
输⼊：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输⼊：head = [] 输出：[]
示例 3：
输⼊：head = [1] 输出：[1]
提示： 链表中节点的数⽬在范围 [0, 100] 内 0 <= Node.val <= 100
前置知识 链表 思路 设置⼀个 dummy 节点简化操作，dummy next 指向 head。
- 初始化 first 为第⼀个节点
- 初始化 second 为第⼆个节点
- 初始化 current 为 dummy
- first.next = second.next
- second.next = first
- current.next = second
- current 移动两格
- 重复
关键点解析
- 链表这种数据结构的特点和使⽤
- dummyHead 简化操作
代码
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function (head) {
const dummy = new ListNode(0);
dummy.next = head;
let current = dummy;
while (current.next != null && current.next.next != null) {
// 初始化双指针
const first = current.next;
const second = current.next.next;
// 更新双指针和 current 指针
first.next = second.next;
second.next = first;
current.next = second;
// 更新指针
current = current.next.next;
}
return dummy.next;
};