单向链表的花式玩法 → 还在玩反转?

发布于 2022年 01月 24日 00:31

开心一刻

  一天,朋友胃疼的难受,陪他去医院

  医生:这些天你都吃了什么?

  朋友:媳妇剩的饭我吃,孩子剩的饭我也吃

  医生:你家不养狗的吗?

  朋友:难道狗剩下的我也要吃?

  我当场就笑岔气了

数据结构

  关于什么是链表,本文不做过多介绍,不了解的小伙伴自行去充能

  稍微带大家回顾下链表的分类,不做过多介绍,直接看图

  单链表

  双向链表

  循环链表

    单向循环链表

    双向循环链表

  环形链表

    由单链表 + 单向循环链表组成

花式玩法

  后续的场景都会基于某些特定类型的链表,大家不要太放飞自我

  我也会在各个场景中明确指明基于那个类型,大家不要看偏了

  单向节点 OneWayNode 

  虽然代码用 java 实现,但涉及到的算法实现是通用的,希望大家不要被开发语言所禁锢

  链表反转

  基本上指的是单链表的反转,大家就认为是单链表的反转

  楼主在以往的面试过程中就遇到过这个问题,而且不止一次被面到

  如果大家连这个都不会,赶紧偷摸 code 起来

  递归实现,实现简单,也好理解

  有递归,往往有其相爱相杀的迭代

  不管是递归还是迭代,变量赋值的顺序不是随便的,不信你们改变下顺序试试

 

  如果没有任何限制,反转实现方式非常多;但面试时,往往会对时间复杂度或空间复杂度做一个极致的考量

  这道题如果出现在面试中,那么考核点就是:时间复杂度 O(N) ,额外空间复杂度 O(1) ,那么你们觉得递归的实现会让面试官满意吗?

  实际开发工程中,反转往往不需要大家手动去实现,高级编程语言基本都有已经实现好的工具方法,大家直接用就好

  例如 java 中有工具方法: Collections.reverse ,有兴趣的可以去跟下自己所用语言的实现,你会有惊喜,会发现有意思的新大陆

  回文判断

  何谓回文,就是反转之后与之前本身一样,例如 a,b,b,a 、 1,2,3,2,1 

  针对该问题,大家第一时间想到的肯定是二分法,但二分法是基于数组的,它不适用于单链表

  那么如何判断单链表的回文了

  那就按回文的描述那样,对原链表进行拷贝,然后反转拷贝的链表,再将原链表与新链表的值逐一对应比较,过程类似如下

  代码如下

  有个数据结构,先进后出,也适用于这个场景,这个数据结构就是:;直接上代码

  利用栈的方式,可以优化,其实只需要入栈链表右半侧的数据即可

  如何控制只入栈链表右半侧的数据了,需要用到快慢指针

  快慢指针的起点都是头结点,慢指针每次移动一个,快指针一次移动两个,当快指针走完的时候,慢指针来到中间位置

  将慢指针所在的链表元素以及慢指针之后的链表元素入栈

  上述的三种方式,不管是哪一种,额外空间复杂度都是 O(N) ,那有没有额外空间复杂度为 O(1) 的方式了

  有,同样用快慢指针,只是快指针走完后,慢指针以及它之后的链表元素不是入栈,而是反转,将反转后的链表与原链表逐一对应比较,如下图所示

  代码实现

  除了有限几个变量,没有使用额外的空间,那么额外空间复杂度就是 O(1) 

  入环节点

  给定一个单向链表(单链表或环形链表中的某一种),判断它是否成环,不成环返回 null ,成环则返回入环的第一个节点

  单链表返回 null ,环形链表则返回入环的第一个节点

  对于题意,相信大家已经理解,那么如何用代码实现了?

  借助 哈希表 ;遍历链表,将节点逐个放入 哈希表 ,放入的时候判断节点是否已存在

  若存在,那么该节点就是入环的第一个节点,若不存在,则将节点放入 哈希表 

  如若链表能遍历完,则说明没有成环,直接返回 null 

  我们来看代码

  就结果而言是对的,但却用了 O(N) 的额外空间复杂度,这往往不是面试官想要的,他想要的往往是 O(1) 的额外空间复杂度

  有没有什么办法可以做到了,肯定是有的: Floyd判圈算法 

  关于 Floyd判圈算法 ,大家自行去百度,它有一个结论:快慢指针第一次在环中相遇时,其中一个指针回到起点,然后两个指针同时一次走一步向后移动,当它们再次相遇时,一定是在第一个入环节点

  我们来简单证明一下这个结论,如下图

  第一次相遇之前,慢指针一次走一步,快指针一次走两步,那么第一次相遇时,快指针走的距离 FD = p + f * c + m,慢指针所走的距离 SD = p + s * c + m

  其中 f 表示快指针在环中走的完整圈数,s 表示慢指针在环中走的完整圈数

  所以 FD = 2 * SD,则有 p + f * c + m = 2 * (p + s * c + m),得到 p + m = (f - 2s) * c

  f - 2s 肯定是一个 >= 0 的整数,所以 p + m 是环形周长的倍数

  快慢指针第一次相遇后,快指针回到起点,慢指针停在相遇点(M),然后快慢指针都每次走一步向后移动

  当快指针来到 P ,快指针走过的距离 FD = p,慢指针走过的距离 SD = p

  因为慢指针是从 M 开始移动的,而 P 离 M 的距离为 m,所以相当于慢指针从 P 开始移动了 p + m 距离

  而前面得出 p + m 就是环形周长的倍数,所以可以理解成慢指针从 P 开始,移动了环形周长倍数的距离,最终还是来到 P

  所以快慢指针相遇于 P,也就是第一个入环节点

  当理解了 Floyd判圈算法 后,代码实现就很简单了

  仅仅用了快慢指针两个额外变量,额外空间复杂度 O(1) 

  这个题其实还有一个变种:如果成环,请返回环的大小(环中有多少个节点)

  求环的大小比找入环的第一个节点要更好理解一点,当快慢指针在环中第一次相遇时,计时器初始成 0,一个指针不动,另一个指针逐步向后移动

  每移动一步计数器就加 1,当快慢指针再次相遇时,计数器的值就是环的大小;代码就不演示了,大家自行去 code 、 code 、 code !

  相交节点

  给定两个单向链表(单链表或环形链表),不相交则返回 null ,相交则返回相交的第一个节点

  借助哈希表,实现比较简单,也容易理解,直接看代码

  额外空间复杂度 O(N) ,这往往不是面试官想要的结果,那有没有什么方式,其额外空间复杂度是 O(1) 了,我们往下看

  我们先来捋一下两个单向链表的关系有哪些

  两个单链表

  如果两个都是单链表,那么他们之间的关系就只有如下两种

  如果两个单链表相交,那么从第一个相交节点开始,后面的节点都是共用的

  所以我们可以如下处理,先找到两个链表的尾节点,如果这两个尾节点不是同一个节点,那么肯定不相交,直接返回 null 

  找尾节点的过程中,记录下两个链表各自的长度:L1、L2,长的链表先移动 | L1-L2 |,然后两个链表同时移动,一次移动一步

  移动的过程中,一旦节点是同一个节点,那么该节点就是相交的第一个节点,直接返回该节点

  结合代码,更好理解

  只用到了有限的几个变量,那么额外空间复杂度 O(1) 

  一个单链表,一个环形链表

  因为链表节点是单向的,所以这两个链表不可能相交

  大家不要无限放大你们丰富的想象力,各种意淫这两个链表的相交情况,结合实际情况去手动画你们脑海中想象出来的相交情况

  链表节点就一个 next 、一个 next 、一个 next !

  两个环形链表

  此时两个链表的关系,无非就下面三种

  两个环形链表的三种情况其实都和入环节点有关系,假设 h1 的入环节点是 loop1,h2 的入环节点是 loop2

  如果 loop1 == loop2,对应情况 2,此时相交的第一个节点肯定在 h1 ~ loop1 或 h2 ~ loop2 之间

    我们可以把 h1 ~ loop1 看成一个单链表,h2 ~ loop2 看成第二个单链表

    此时大家是不是想起了什么,往上滑一滑,去看看 两个单链表 的相交

  如果 loop1 != loop2,对应情况 1、3

    从 loop1 的下一个节点开始,一次走一步,如果回到了 loop1 还未遇到 loop2,那么两个链表不相交

    如果回到 loop1 之前遇到了 loop2,那么说明两个链表相交,第一个相交的节点就是 loop1 或 loop2

  我们来看看代码

  把 两个单向链表 的三种关系串起来

  额外空间复杂度 O(1) 

  有没有觉得很好玩 ?

总结

  1、一个题的实现方式往往有多种,但面试中往往考核的是时间复杂度或空间复杂度的极致利用

  2、快慢指针在链表中很重要,希望大家能够建立起快慢指针的概念

  3、链表的花式玩法非常多,有兴趣的可以去力扣上刷一刷:链表

推荐文章