引入
上一节,我们学习了尾指针,并且利用尾指针。尾指针可以轻松的操作头结点和尾结点,可以将两个单循环链表组成了一个单循环链表,我们今天再看看,尾指针还有什么其它玩法。
单链表中的环
首先要明白,单链表有环的状态是什么样子得
其实就是,尾指针指向了链表中的某个结点。
如何判断单链表中是否有环
方法 1
- 设置 p 、q 两个指针
- p 向前走,q 从头走,p 向前走尾部应该会到 NULL。
- 每个结点,p 走的步数应该和 q 一样
- 如果不一样,就像上面的图,p 的地址等于 q
- 但是,p 走到3用了6步,q 则用了2步
- 步数不相等,那么就存在环
方法 2
- 设置 p 、q 两个指针
- p 每走一步,q 就走两步,快慢指针
- 快指针应该很快到 NULL
- 如果 p==q 了,则存在环
代码实现
1 |
|
代码实现的主要思路就是
- A 指针走一步
- B 也走,循环遍历,什么时候走的地址等于 A 走的这一步的地址了
- 就判断,A 走的这一步的步数等于不等于 B 走的步数
- 如果地址相等、步数相等,那OK!
- 如果地址相等,步数不等,那 B 肯定抄近路走环了
- 就把 b 当前得步数输出出来就行了!,这就是出问题的结点
用快慢指针实现
1 |
|
用快慢指针的方法大概思路如下
- 因为normal要移动1位,fast 移动2位
- 要判断 fast 移动的这两位是否为 NULL 了
- 如果为 NULL,则一定没有环
- 如果不为 NULL,那就继续比较
- 直到地址相同或者遇到 NULL 为止
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。