目录
第21题. Merge Two Sorted Lists
解法一 迭代
解法二 递归
总
第22题 . Generate Parentheses
1. 题目描述（中等难度）
解法一 暴力破解
解法二
解法三
扩展 卡塔兰数
总
第23题: Merge k Sorted Lists
解法一 暴力破解
解法二 一列一列比较
解法三 优先队列
解法四 两两合并
解法五 两两合并优化
总
第24题: Swap Nodes in Pairs
解法一 迭代
解法二 递归
总
第25题 : Reverse Nodes in k-Group
解法一 迭代
解法二递归
总
喜欢 请点个 + 关注
第21题. Merge Two Sorted Lists
题目描述（简单难度）
合并两个有序链表。
解法一 迭代
遍历两个链表。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode h = new ListNode(0); ListNode ans=h; while (l1 != null && l2 != null) { if (l1.val < l2.val) { h.next = l1; h = h.next; l1 = l1.next; } else { h.next = l2; h = h.next; l2 = l2.next; } } if(l1==null){ h.next=l2; } if(l2==null){ h.next=l1; } return ans.next; }
时间复杂度：O（m + n）。
空间复杂度：O（1）。
解法二 递归
参考[这里](https://leetcode.wang/Merge Two Sorted Lists)
ListNode mergeTwoLists(ListNode l1, ListNode 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(l2.next, l1); return l2; } }
时间复杂度：
空间复杂度：
总
递归看起来，两个字，优雅！但是关于递归的时间复杂度，空间复杂度的求法，先留个坑吧。
第22题 . Generate Parentheses
1. 题目描述（中等难度）
给一个数字 n ，返回所有合法的括号匹配，刚好和[20题](https://leetcode.wang/leetCode-20-Valid Parentheses.html)相反。
自己没想出来，全部参考 LeetCode 给出的 Solution。
解法一 暴力破解
列举所有的情况，每一位有左括号和右括号两种情况，总共 2n 位，所以总共 22n2^{2n}22n 种情况。
public List<String> generateParenthesis(int n) { List<String> combinations = new ArrayList(); generateAll(new char[2 * n], 0, combinations); return combinations; } public void generateAll(char[] current, int pos, List<String> result) { if (pos == current.length) { if (valid(current)) result.add(new String(current)); } else { current[pos] = '('; generateAll(current, pos+1, result); current[pos] = ')'; generateAll(current, pos+1, result); } } public boolean valid(char[] current) { int balance = 0; for (char c: current) { if (c == '(') balance++; else balance--; if (balance < 0) return false; } return (balance == 0); }
时间复杂度：对每种情况判断是否合法需要 O（n），所以时间复杂度是 O(22nn)O(2^{2n}n)O(22nn) 。
空间复杂度：O(22nn)O(2^{2n}n)O(22nn)，乘以 n 是因为每个串的长度是 2n。此外这是假设所有情况都符合的时候，但其实不可能都符合，后边会给出更精确的情况。
解法二
解法一中，我们不停的加左括号，其实如果左括号超过 n 的时候，它肯定不是合法序列了。因为合法序列一定是 n 个左括号和 n 个右括号。
还有一种情况就是如果添加括号的过程中，如果右括号的总数量大于左括号的总数量了，后边不论再添加什么，它都不可能是合法序列了。因为每个右括号必须和之前的某个左括号匹配，如果右括号数量多于左括号，那么一定有一个右括号没有与之匹配的左括号，后边不论加多少左括号都没有用了。例如 n = 3 ，总共会有 6 个括号，我们加到 ( ) ) 3 个括号的情况的时候，有 1 个左括号，2 个右括号，此时后边 3 个括号无论是什么，已经注定它不会是合法序列了。
基于上边的两点，我们只要避免它们，就可以保证我们生成的括号一定是合法的了。
public List<String> generateParenthesis(int n) { List<String> ans = new ArrayList(); backtrack(ans, "", 0, 0, n); return ans; } public void backtrack(List<String> ans, String cur, int left, int right, int n){ if (cur.length() == n * 2) { ans.add(cur); return; } //左括号不要超过 n if (left < n) backtrack(ans, cur+"(", left+1, right, n); //右括号不要超过左括号 if (right < left) backtrack(ans, cur+")", left, right+1, n); }
时间复杂度：
空间复杂度：
递归的复杂度分析，继续留坑 =.=。
解法三
解法二中是用列举的方法，仔细想想，我们每次用递归的时候，都是把大问题换成小问题然后去解决，这道题有没有这个思路呢？
我们想一下之前的列举过程，第 0 个位置一定会是左括号，然后接着添加左括号或右括号，过程中左括号数一定大于或等于右括号数，当第一次出现左括号数等于右括号数的时候，假如此时的位置是 c 。那么位置 1 到 c - 1 之间一定是合法序列，此外 c + 1 到最后的 2n -1 也是合法序列。而假设总共是 n 组括号，1 到 c - 1 是 a 组括号， c + 1 到 2n - 1 之间则是 n - 1 - a 组括号，如下图
a = 1，b = 1，对应 （（））（（）） 一种情况，此时 c = 3。
a = 2，b = 0 对应 （（（）））， （（）（）） 两种情况，此时 c = 5。
所以我们如果要想求 n 组括号，只需要知道 a 组和 b 组的情况，然后组合起来就可以了。
看起来我们在迭代 a ，其实本质上是在迭代 c ，c = 2a + 1，迭代 a 从 0 到 n - 1 ，就是迭代 c 从 1 到 2n - 1。看起来 c 都是奇数，其实是可以理解的，因为 0 到 c 间都是一组组的括号， 所以 c 一定是奇数。为什么可以迭代 c ，因为上边说到每一个合法序列都对应着一个 c ，遍历 c 的话，就能得到所有的情况了，看一下代码吧。
public List<String> generateParenthesis(int n) { List<String> ans = new ArrayList(); if (n == 0) { ans.add(""); } else { for (int a = 0; a < n; a++) for (String left: generateParenthesis(a)) for (String right: generateParenthesis(n-1-a)) ans.add("(" + left + ")" + right); } return ans; }
时间复杂度：
空间复杂度：
留坑。
扩展 卡塔兰数
如果这道题不是让你列举所有的情况， 而是仅仅让你输出 n 对应下有多少种合法序列，该怎么做呢？
答案就是 1n+1C2nn\frac{1}{n+1}C^n_{2n}n+11C2nn，也可以写成1n+1(2nn)\frac{1}{n+1}\binom{2n}{n}n+11(n2n)。怎么证明呢？我主要参考了这里，说一下。
我们假设不考虑是不是合法序列，那么就一共有C2nnC^n_{2n}C2nn种情况，然后我们只需要把里边的非法情况减去就可以了，一共有多少种非法情况呢？
首先我们用C2nnC^n_{2n}C2nn就保证了一定是有 n 个左括号，n 个右括号，那么为什么出现了非法序列？
为了方便论述，我们把左括号记为 +1，右括号记为 -1.
ps：下边的 和 都是指两个数的和，不是你和我中的和。
我们假设非法序列的集合是 M ，而非法序列就是列举过程中右括号数比左括号数多了，也就是和小于 0 了，变成 -1 了。这种情况一旦出现，后边无论是什么括号都改变不了它是非法序列的命了。我们将第一次和等于 -1 的时候的位置记为 d 。每一个非法序列一定存在这样一个 d 。然后关键的地方到了！
此时我们把 0 到 d 所有的 -1 变成 1，1 变成 -1，我们将每一个非法序列都这样做，就构成了一个新的集合 N ，并且这个集合 N 一定和 M 中的元素一一对应（ N -> M，在集合 N 中第一次出现和为 1 的位置也就是 d ，把 0 到 d 中所有的 -1 变成 1，1 变成 -1 就回到了 M），从而集合 M 的数量就等于集合 N 的数量。集合 N 的数量是多少呢？
我们来分析下集合 N 是什么样的，集合 N 对应的集合 M 原来的序列本来是这样的，在 0 到 d 之间和是 -1 ，也就是 -1 比 +1 多一个，d + 1 到最后的和一定是 1（因为 n 个 +1 和 n 个 -1 的和一定是 0 ，由于 0 到 d 和是 -1，后边的和一定是 1），也就意味着 +1 比 -1 多一个。而在集合 N 中，我们把 0 到 d 的 -1 变成了 +1 ，+1 变成了 -1 ，所以也变成了 +1 比 -1 多一个，所以集合 N 总共就是 +1 比 -1 多 2 个的集合，也就是 n + 1 个 +1 和 n - 1 个 -1 。
所以集合 N 就是 2n 个位置中选 n - 1 个位置放 -1，其他位置放 +1，总共就有 C2nn−1C^{n - 1}{2n}C2nn−1，所以集合 M 也有 C2nn−1C^{n - 1}{2n}C2nn−1种。
所有合法序列就有 C2nn−C2nn−1=1n+1C2nnCn_{2n}-C{n-1}{2n}=\frac{1}{n+1}C^n{2n}C2nn−C2nn−1=n+11C2nn 。
将集合 M 和集合 N 建立了一一映射，从而解决了问题，神奇！！！！！！！！！！其实，这个数列就是卡塔兰数，可以看下维基百科的定义。
而这个数列，其实除了括号匹配，还有很多类似的问题，其本质是一样的，例如，
2n 个人排队买票，其中 n 个人持 50 元，n 个人持 100 元。每张票 50 元，且一人只买一张票。初始时售票处没有零钱找零。请问这 2n 个人一共有多少种排队顺序，不至于使售票处找不开钱？
对于一个无限大的栈，一共n个元素，请问有几种合法的入栈出栈形式？
P = a1 a2 a3 … an，其中 ai 是矩阵。根据乘法结合律，不改变矩阵的相互顺序，只用括号表示成对的乘积，试问一共有几种括号化方案？
n 个结点可构造多少个不同的二叉树？
… …
更多例子可以看维基百科和这里。
而 Solutin 给出的时间复杂度，其实就是卡特兰数。
维基百科的给出的性质。
总
本以为这道题挺常规的，然后自己一直卡在解法三的理解上，查来查去，竟然查出了卡塔兰数，虽然似乎和解法三也没什么关系，但又开阔了很多思路。解法三分析出来的迭代方法，以及用映射证明卡塔兰数的求法，棒！
第23题: Merge k Sorted Lists
- 题目描述（困难难度）
k 个有序链表的合并。
我们用 N 表示链表的总长度，考虑最坏情况，k 个链表的长度相等，都为 n 。
解法一 暴力破解
简单粗暴，遍历所有的链表，将数字存到一个数组里，然后用快速排序，最后再将排序好的数组存到一个链表里。
public ListNode mergeKLists(ListNode[] lists) { List<Integer> l = new ArrayList<Integer>(); //存到数组 for (ListNode ln : lists) { while (ln != null) { l.add(ln.val); ln = ln.next; } } //数组排序 Collections.sort(l); //存到链表 ListNode head = new ListNode(0); ListNode h = head; for (int i : l) { ListNode t = new ListNode(i); h.next = t; h = h.next; } h.next = null; return head.next; }
时间复杂度：假设 N 是所有的数字个数，存到数组是 O（N），排序如果是用快速排序就是 O(NlogN)O(Nlog_N)O(NlogN) ，存到链表是 O（N），所以取个最大的，就是 O(NlogN)O(Nlog_N)O(NlogN)。
空间复杂度：新建了一个链表，O（N）。
解法二 一列一列比较
我们可以一列一列的比较，将最小的一个存到一个新的链表里。
public ListNode mergeKLists(ListNode[] lists) { int min_index = 0; ListNode head = new ListNode(0); ListNode h = head; while (true) { boolean isBreak = true;//标记是否遍历完所有链表 int min = Integer.MAX_VALUE; for (int i = 0; i < lists.length; i++) { if (lists[i] != null) { //找出最小下标 if (lists[i].val < min) { min_index = i; min = lists[i].val; } //存在一个链表不为空，标记改完 false isBreak = false; } } if (isBreak) { break; } //加到新链表中 ListNode a = new ListNode(lists[min_index].val); h.next = a; h = h.next; //链表后移一个元素 lists[min_index] = lists[min_index].next; } h.next = null; return head.next; }
时间复杂度：假设最长的链表长度是 n ，那么 while 循环将循环 n 次。假设链表列表里有 k 个链表，for 循环执行 k 次，所以时间复杂度是 O（kn）。
空间复杂度：N 表示最终链表的长度，则为 O（N）。
其实我们不需要创建一个新链表保存，我们只需要改变得到的最小结点的指向就可以了。
public ListNode mergeKLists(ListNode[] lists) { int min_index = 0; ListNode head = new ListNode(0); ListNode h = head; while (true) { boolean isBreak = true; int min = Integer.MAX_VALUE; for (int i = 0; i < lists.length; i++) { if (lists[i] != null) { if (lists[i].val < min) { min_index = i; min = lists[i].val; } isBreak = false; } } if (isBreak) { break; } //最小的节点接过来 h.next = lists[min_index]; h = h.next; lists[min_index] = lists[min_index].next; } h.next = null; return head.next; }
时间复杂度：假设最长的链表长度是 n ，那么 while 循环将循环 n 次。假设链表列表里有 k 个链表，for 循环执行 k 次，所以时间复杂度是 O（kn）。
空间复杂度：O（1）。
解法三 优先队列
解法二中，我们每次都是取出一个最小的，然后加入一个新的， O（1）的复杂度，再找最小的，O（k） 的复杂度。我们完全可以用一个优先队列。
我们将优先级定义为数越小优先级越高，如果用堆实现优先队列，这样我们每次找最小不再需要 O（k），而是 O（log（k）），当然这样的话，我们加入新的话不再是 O（1），也需要 O（log（k））。可以看看这里和这里。
public ListNode mergeKLists(ListNode[] lists) { //定义优先队列的比较器 Comparator<ListNode> cmp; cmp = new Comparator<ListNode>() { @Override public int compare(ListNode o1, ListNode o2) { // TODO Auto-generated method stub return o1.val-o2.val; } }; //建立队列 Queue<ListNode> q = new PriorityQueue<ListNode>(cmp); for(ListNode l : lists){ if(l!=null){ q.add(l); } } ListNode head = new ListNode(0); ListNode point = head; while(!q.isEmpty()){ //出队列 point.next = q.poll(); point = point.next; //判断当前链表是否为空，不为空就将新元素入队 ListNode next = point.next; if(next!=null){ q.add(next); } } return head.next; }
时间复杂度：假如总共有 N 个节点，每个节点入队出队都需要 log（k），所有时间复杂度是 O（N log（k））。
空间复杂度：优先队列需要 O（k）的复杂度。
解法四 两两合并
利用之前合并两个链表的算法，我们直接两两合并，第 0 个和第 1 个链表合并，新生成的再和第 2 个链表合并，新生成的再和第 3 个链表合并…直到全部合并完。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode h = new ListNode(0); ListNode ans=h; while (l1 != null && l2 != null) { if (l1.val < l2.val) { h.next = l1; h = h.next; l1 = l1.next; } else { h.next = l2; h = h.next; l2 = l2.next; } } if(l1==null){ h.next=l2; } if(l2==null){ h.next=l1; } return ans.next; } public ListNode mergeKLists(ListNode[] lists) { if(lists.length==1){ return lists[0]; } if(lists.length==0){ return null; } ListNode head = mergeTwoLists(lists[0],lists[1]); for (int i = 2; i < lists.length; i++) { head = mergeTwoLists(head,lists[i]); } return head; }
时间复杂度：不妨假设是 k 个链表并且长度相同，链表总长度为 N，那么第一次合并就是 N/k 和 N/k ，第二次合并就是 2 * N/k 和 N/k，第三次合并就是 3 * N/k 和 N / k，总共进行 n - 1 次合并，每次合并的时间复杂度是 O（n），所以总时间复杂度就是O(∑i=1k−1(i∗Nk+Nk))=O(kN)O(\sum_{i=1}^{k-1}(i*\frac{N}{k}+\frac{N}{k}))=O(kN)O(∑i=1k−1(i∗kN+kN))=O(kN)，可以将两项分开，N/k 其实是常数，分开的第一项是等差数列。
空间复杂度：O（1）。
解法五 两两合并优化
依旧假设是 k 个链表，合并的过程优化下，使得只需要合并 log（k）次。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode h = new ListNode(0); ListNode ans=h; while (l1 != null && l2 != null) { if (l1.val < l2.val) { h.next = l1; h = h.next; l1 = l1.next; } else { h.next = l2; h = h.next; l2 = l2.next; } } if(l1==null){ h.next=l2; } if(l2==null){ h.next=l1; } return ans.next; } public ListNode mergeKLists(ListNode[] lists) { if(lists.length==0){ return null; } int interval = 1; while(interval<lists.length){ System.out.println(lists.length); for (int i = 0; i + interval< lists.length; i=i+interval*2) { lists[i]=mergeTwoLists(lists[i],lists[i+interval]); } interval*=2; } return lists[0]; }
时间复杂度：假设每个链表的长度都是 n ，有 k 个链表，记总结点数是 N = n * k，那么时间复杂度就是O(∑i=1log2kN)=O(Nlogk)O(\sum_{i=1}^{log_2k}N)=O(Nlogk)O(∑i=1log2kN)=O(Nlogk)。
空间复杂度：O（1）。
总
优先队列的运用印象深刻，此外对两两链表的合并，我们仅仅改变了合并的方式就将时间复杂度降低了很多，美妙！
第24题: Swap Nodes in Pairs
题目描述（中等难度）
给定一个链表，然后两两交换链表的位置。
解法一 迭代
首先为了避免单独讨论头结点的情况，一般先申请一个空结点指向头结点，然后再用一个指针来遍历整个链表。
先来看一下图示：
point 是两个要交换结点前边的一个位置。
public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode point = dummy; while (point.next != null && point.next.next != null) { ListNode swap1 = point.next; ListNode swap2 = point.next.next; point.next = swap2; swap1.next = swap2.next; swap2.next = swap1; point = swap1; } return dummy.next; }
时间复杂度：O（n）。
空间复杂度：O（1）。
解法二 递归
参考这里。
自己画了个参考图。
public ListNode swapPairs(ListNode head) { if ((head == null)||(head.next == null)) return head; ListNode n = head.next; head.next = swapPairs(head.next.next); n.next = head; return n; }
递归时间复杂度留坑。
总
自己开始没有想出递归的算法，每次都会被递归的简洁吸引。另外，感觉链表的一些题，只要画图打打草稿，搞清指向关系，一般不难。
第25题 : Reverse Nodes in k-Group
题目描述（困难难度）
将一个链表，每 k 个倒置，最后一组不足 k 个就不倒置。
解法一 迭代
关于单链表倒置，我们在第 2 题就讨论过。有了单链表倒置，这道题无非就是用一个循环，每次将 k 个结点取下来，倒置后再接回去，然后再取 k 个，以此循环，到了最后一组如果不足 k 个，不做处理，直接返回头结点就可以了。所以关键就是，指针指来指去，大家不晕掉就好，我做了图示，大家参考一下。
为了将头结点也一般化，我们创建一个 dummy 结点，然后整个过程主要运用三个指针， tail 指针表示已经倒置后的链表的尾部，subhead 指针表示要进行倒置的子链表，toNull 指针为了将子链表从原来链表中取下来。
一个 while 循环，让 toNull 指针走 k - 1 步使其指向子链表的尾部。中间的 if 语句就是判断当前节点数够不够 k 个了，不够的话直接返回结果就可以了
将子链表指向 null ，脱离出来。并且用 temp 保存下一个结点的位置。
然后调用倒置函数，将子链表倒置。
接下来四步分别是，新链表接到 tail（注意下边的图 tail 是更新后的位置，之前 tail 在 dummy 的位置） 的后边；更新 tail 到新链表的尾部，也就是之前的 subhead （下图 subhead 也是更新后的位置，之前的位置参见上边的图）；sub_head 更新到 temp 的位置；toNull 到 sub_head 的位置；然后将新的尾部 tail 把之前断开的链表连起来，接到 sub_head 上。
整理下其实就是下边的样子
和初始的时候（下边的图）对比一下，发现 tail，subhead 和 toNull 三个指针已经就位，可以愉快的重复上边的步骤了。
看下代码吧。
public ListNode reverseKGroup(ListNode head, int k) { if (head == null) return null; ListNode sub_head = head; ListNode dummy = new ListNode(0); dummy.next = head; ListNode tail = dummy; ListNode toNull = head; while (sub_head != null) { int i = k; //找到子链表的尾部 while (i - 1 > 0) { toNull = toNull.next; if (toNull == null) { return dummy.next; } i--; } ListNode temp = toNull.next; //将子链表断开 toNull.next = null; ListNode new_sub_head = reverse(sub_head); //将倒置后的链表接到 tail 后边 tail.next = new_sub_head; //更新 tail tail = sub_head; //sub_head 由于倒置其实是新链表的尾部 sub_head = temp; toNull = sub_head; //将后边断开的链表接回来 tail.next = sub_head; } return dummy.next; } public ListNode reverse(ListNode head) { ListNode current_head = null; while (head != null) { ListNode next = head.next; head.next = current_head; current_head = head; head = next; } return current_head; }
时间复杂度：while 循环中本质上我们只是将每个结点访问了一次，加上结点倒置访问的一次，所以总共加起来每个结点其实只访问了 2 次。所以时间复杂度是 O（n）。
空间复杂度：O（1）。
解法二递归
有没有被解法一的各种指针绕晕呢，我们有一个更好的选择，递归，这样看起来就会简洁很多。
public ListNode reverseKGroup(ListNode head, int k) { if (head == null) return null; ListNode point = head; //找到子链表的尾部 int i = k; while(i - 1 >0){ point = point.next; if (point == null) { return head; } i--; } ListNode temp = point.next; //将子链表断开 point.next = null; //倒置子链表，并接受新的头结点 ListNode new_head = reverse(head); //head 其实是倒置链表的尾部，然后我们将后边的倒置结果接过来就可以了 //temp 是链表断开后的头指针，可以参考解法一的图示 head.next = reverseKGroup(temp,k); return new_head; } public ListNode reverse(ListNode head) { ListNode current_head = null; while (head != null) { ListNode next = head.next; head.next = current_head; current_head = head; head = next; } return current_head; }
复杂度：递归留坑。
总
还是那句话，涉及到链表的，我们就画下图，把各个指针的移动理清楚，一般没啥问题。
今天我们一起学习了LeetCode 题的算法分析,感谢大家阅读,觉得不错记得收藏哦!
