写点什么

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

用户头像
Android架构
关注
发布于: 12 小时前

前言

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

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 的功能就是把二叉树变成双向链表,例如对于这种一棵二叉树:

用户头像

Android架构

关注

还未添加个人签名 2021.10.31 加入

还未添加个人简介

评论

发布
暂无评论
链表问题不会做?LC狂刷50道链表算法总结出这9道典型题,套路很简单(二