链表问题不会做？LC 狂刷 50 道链表算法总结出这 9 道典型题，套路很简单（二

前言

续上前篇链表典型题。错过的朋友可以关注我，在我的主页查看学习。废话不多说，我们直接上干货。（很干，建议备好白开水）

5、将单向链表按某值划分成左边小，中间相等，右边大的形式 md

【题目描述】

给定一个单向链表的头结点 head,节点的值类型是整型，再给定一个整数 privot。实现一个调整链表的函数，将链表调整为左部分都是值小于 privot 的节点，中间部分都是值等于 privot 的节点，右部分都是大于 privot 的节点。且对某部分内部节点的顺序不做要求

例如:链表 9-0-4-5-1，pivot=3。

调整后是 1-0-4-9-5，

也可以是 0-1-9-5-4

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【解答】

这道题在思路上还是比较简单的，但是在实现上还是有一些细节需要主要的。

本题对某部分的内部节点不做要求，一种很简单的方法就是用一个数组来存链表的节点，然后像类似于快速排序的分割函数那样，按照某个值把他们进行划分。

不过这样做的话，空间复杂度为 O(N)。我们也可以采取使用 3 个指针，把原链表依次划分成三个部分的链表，然后再把他们合并起来，这种做法不但空间复杂度为 O(1), 而且内部节点的顺序也是和原链表一样的。虽然思路简单，但在代码实现上也是有很多细节需要注意的，有时间的话希望大家动手打下码。

代码如下：

//用三个指针处理，这道题主要是要注意串联链表时的一些细节处理 public static Node listPartition(Node head, int pivot) {Node sB = null;//小的指针头，即 small beginNode sE = null;//小的指针尾，即 small endNode eB = null;//中的指针头，即 equal beginNode eE = null;//中的指针尾，即 emall endNode bB = null;//大的指针头，即 big beginNode bE = null;//大的指针尾，即 big endNode next = null;//保存下一个节点//进行划分 while (head != null) {next = head.next;head.next = null;if (head.value < pivot) {if (sB == null) {sB = head;sE = head;} else {sE.next = head;sE = sE.next;}} else if (head.value == pivot) {if (eB == null) {eB = head;eE = head;} else {eE.next = head;eE = eE.next;}} else {if (bB == null) {bB = head;bE = head;} else {bE.next = head;bE = bE.next;}}head = next;}//把三部分串连起来，串联的时候细节还是挺多的，//串联的过程下面代码的精简程度是最学习的部分了

//1.小的与中的串联 if (sB != null) {sE.next = eB;eE = eE == null ? sE : eE;}//2.中的和大的连接 if (eB != null) {eE.next = bB;}return sB != null ? sB : eB != null ? eB : bB;}

6、复制含有随机指针节点的链表

【题目描述】

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【解答】

方法一：使用额外的存储空间

这道题的难点在于我们需要定位好随机指针，一个比较简单的解法就是把原节点与复制的节点关联起来，可以使用哈希表把他们关联起来。

首先把副节点全部创建出来，然后把原节点与对应的副节点用哈希表关联起来。关联的时候原节点作为 key，副节点作为 value。例如对于链表 1->2->3->null。创建副节点 1', 2', 3'。然后用哈希表关联起来：

key | value ---|--- 1 | 1' 2 | 2' 3 | 3'

之后在把所有副节点连接成一个链表。在连接的时候，我们 可以通过哈希表很容易这找到对应的随机节点。

代码如下

//方法 1：采用哈希表 public static Node1 copyListWithRand(Node1 head) {Map<Node1, Node1> map = new HashMap<>();Node1 cur = head;while (cur != null) {map.put(cur, new Node1(cur.value));cur = cur.next;}//把副节点连接起来 cur = head;while (cur != null) {map.get(cur).next = map.get(cur.next);map.get(cur).rand = map.get(cur.rand);cur = cur.next;}return map.get(head);}

这种方法的时间复杂度为 O(n), 空间复杂度也为 O(n)。

方法 2

其实我们也可以不需要哈希表来辅助，也就是说 ，我们是可以做到空间复杂度为 O(1)的，我们可以把复制的副节点插入到原链表中去，这样也能把原节点与副节点进行关联，进而 定位到随机节点。例如，对于链表 1->2->3->null。首先生成副节点 1', 2', 3。然后把副节点插入到原节点的相邻位置，即把原链表变成 1->1'->2->2'->3->3'->null。

这样我们也可以在连接副节点的时候，找到相应的随机节点。例如 1 的随机节点是 3，则 1' 的随机节点是 3'。显然，1 节点的随机节点的下一个节点就是 1'的随机节点。具体代码如下：

//方法二 public static Node1 copyListWithRand2(Node1 head){Node1 cur = head;Node1 next = null;

//把复制的节点插进去 while (cur != null) {next = cur.next;Node1 temp = new Node1(cur.value);//复制节点 temp.next = cur.next;cur.next = temp;cur = next;}//在一边把复制的节点取出来一边连接。cur = head;next = null;while (cur != null) {next = cur.next.next;//保存原链表的下一个节点 cur.next.next = next != null ? next.next : null;cur.next.rand = cur.rand != null ? cur.rand.next : null;cur = next;}return head.next;}

采用这种方法的时候，由于随机节点有可能是空指针，随意写代码的时候要注意。

7、将单链表的每 K 个节点之间逆序

【题目描述】

给定一个单链表的头节点 head, 实现一个调整单链表的函数，使得每 K 个节点之间逆序，如果最后不够 K 个节点一组，则不调整最后几个节点。

例如：

链表:1->2->3->4->5->6->7->8->null, K = 3。

调整后：3->2->1->6->5->4->7->8->null。其中 7，8 不调整，因为不够一组。

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【解答】

这道题我们可以用递归来实现，假设方法 reverseKNode()的功能是将单链表的每 K 个节点之间逆序。reverse()方法的功能是将一个单链表逆序。

那么对于下面的这个单链表，其中 K = 3。

我们把前 K 个节点与后面的节点分割出来：

temp 指向的剩余的链表，可以说是原问题的一个子问题。我们可以调用 reverseKNode()方法将 temp 指向的链表每 K 个节点之间进行逆序。再调用 reverse()方法把 head 指向的那 3 个节点进行逆序，结果如下：

接着，我们只需要把这两部分给连接起来就可以了。最后的结果如下：

如果不大理解，看下代码可能就比较好理解了。

代码如下

//每 k 个节点为一组的逆转 public static Node reverseKNodes(Node head, int k) {if (head == null || head.next == null) {return head;}Node cur = head;for (int i = 1; cur != null && i < k; i++) {

《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
浏览器打开：qq.cn.hn/FTe 免费领取

cur = cur.next;}//判断是否能组成一组。if (cur == null) {return head;}//temp 指向剩余的链表 Node temp = cur.next;cur.next = null;//把 k 个节点进行反转 Node newHead = reverse(head);//把之后的部分链表进行每 K 个节点逆转转 Node newTemp = reverseKNodes(temp, k);//把两部分节点连接起来 return newHead;}

//单链表逆序 public static Node reverse(Node head) {if (head == null || head.next == null) {return head;}Node newHead = reverse(head.next);head.next.next = head;head.next = null;return newHead;}

当然，这道题一个很简单的做法就是利用栈来辅助，每 K 个节点入栈就把这 K 个节点出栈连接成一个链表，之后剩余再在进栈.....

不过这种做法的额外空间复杂度是 O(K)。

8、将搜索二叉树转换成双向链表

【题目描述】

对于二叉树的节点来说，有本身的值域，有指向左孩子和右孩子的两个指针；对双向链表的节点来说，有本身的值域，有指向上一个节点和下一个节点的指针。在结构上，两种结构有相似性，现有一棵搜索二叉树，请将其转为成一个有序的双向链表。 　 节点定义：

class Node2{public int value;public Node2 left;public Node2 right;

public Node2(int value) {this.value = value;}}

例如：

这棵二叉搜索树转换后的双向链表从头到尾依次是 1～9。对于每一个节点来说，原来的 right 指针等价于转换后的 next 指针，原来的 left 指针等价于转换后的 last 指针，最后返回转换后的双向链表的头节点。

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)

【解答】

方法一：采用队列辅助

如果用一个队列来辅助的话，还是挺容易。采用中序遍历的方法，把二叉树的节点全部放进队列，之后在逐一弹出来连接成双向链表。

代码如下

public static Node2 convert1(Node2 head) {Queue<Node2> queue = new LinkedList<>();//将节点按中序遍历放进队列里 inOrderToQueue(head, queue);head = queue.poll();Node2 pre = head;pre.left = null;Node2 cur = null;while (!queue.isEmpty()) {cur = queue.poll();pre.right = cur;cur.left = pre;pre = cur;}pre.right = null;return head;}

private static void inOrderToQueue(Node2 head, Queue<Node2> queue) {if (head == null) {return;}inOrderToQueue(head.left, queue);queue.offer(head);inOrderToQueue(head.right, queue);}

这种方法的时间复杂度为 O(n), 空间复杂度也为 O(n)。

方法 2：通过递归的方式

在之前打卡的 9 道题中，几乎超过一般都用到了递归，如果这些题目使用的递归大家都理解了，并且能够自己独立写出代码了，那么我相信大家对递归的思想、使用已经有一定的熟练性。

我们假设函数 conver 的功能就是把二叉树变成双向链表，例如对于这种一棵二叉树：