本文主要是介绍天下三分明月夜,独有快慢指针法(链表面试题篇),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
本篇会加入个人的所谓‘鱼式疯言’
❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言
而是理解过并总结出来通俗易懂的大白话,
小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.
🤭🤭🤭可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念 !!!
前言
本篇文章是小编 刷题篇 的开篇鼻祖, 想要学好编程,小伙们的刷题是必不可少的,这次小编更重磅出击,以 “鱼式疯言” 和 动图 的形式带着小伙们更好的理解我们解题方法是过程
主要内容是讲解我们 快慢指针 这个解题方法对于某些链表题型的堪称秒杀的存在 💥 💥 💥
下面就让充满知识双眼的宝子们一起来瞧瞧呗 💖 💖 💖
特此声明在本系列文章中将以面试题为载体展开解题方法的实际运用的(题目来源于力扣或牛客刷题网站)
目录
-
寻找链表的中间结点
-
判断链表是否带环
-
返回链表倒数第k个节点
一. 寻找链表的中间结点
寻找链表的中间结点题目链接
1. 题目描述
2. 解题思路
看到此题,小伙伴的第一想法肯定是 遍历链表长度,然后进行在走一半的长度即可到达我们的中间节点
但小编的这里有个独特的解法就是我们的双指针法
如果 节点数是奇数时
如果 节点数是偶数时
这个就是我们的快慢指针法,简单说明下就是,
先让 fast指针先走两步,然后slow指针走一步
但 快指针走到下一个节点或者是自身是null时,slow指针的位置就是我们的中间节点
3. 题解代码(Java)
class Solution {public ListNode middleNode(ListNode head) {if(head==null) {return head;}ListNode cur=head,prev=head;while(cur != null && cur.next != null) {prev=prev.next;cur=cur.next.next;}return prev;}
}
为啥我们的一个走两步,一个走一步就能找到中间的节点呢 ? ? ?
这其实是一个 数学问题
鱼式疯言
细节注意
cur != null && cur.next != null
这两个条件可以交换 顺序不 ,答案是 不可以的
如果交换了
当cur=null 时就会造成 cur.next 空异常
而我们的正常顺序时
当 cur != null 时会造成短路就不引起后面的 空指针异常
二. 判断链表是否带环
判断链表是否带环题链接
1. 题目描述
2. 解题思路
小伙伴们可以思考一个问题,我们当我们的 节点往后走 ,那怎么找到他们 重合的位置呢
是的,这里我们还是用到了快慢指针的方法
当 fast 指针走二步, slow 指针走一步时,利用他们俩相差一步的距离就可找到重复的节点,从而重合
3.题解代码
public class Solution {public boolean hasCycle(ListNode head) {if(head==null) {return false;}ListNode slow=head;ListNode fast=head;while(fast != null && fast.next != null) {fast=fast.next.next;slow=slow.next;if(fast== slow) {return true;}}return false;}
}
详细说明下
快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从 链表起始位置 开始运行
如果链表带环则一定会在 环中相遇,否则快指针率先走到 链表的末尾 。
鱼式疯言
如果我们这样考虑是否可以呢
如果 fast 走三步,slow走一步 会发生什么呢
很明显两者是不能相遇的
所以小编的建议是 用 fast 走两步 ,slow走一步 来 解题更妥当 ❣️ ❣️ ❣️
三. 返回链表倒数第k个节点
返回链表倒数第k个节点题目链接
1. 题目描述
2. 解题思路
还是运用快慢指针的思路:
先让fast 走 k-1 步 ,然后再 在 fast 和 slow 指针一起走 ,直到快指针的 next 为 null
3. 题解代码
class Solution {public int kthToLast(ListNode head, int k) {ListNode slow=head,fast=head;int i=0;while(fast != null) {if(i<k) {fast=fast.next;i++;} else {fast=fast.next;slow=slow.next;}}if(i<k || k<0) {return -1;}return slow.val;}}
小伙伴们有思考过这背后的原理是什么么?
是的,让快指针走 k-1 是形成路程差,再一起走的时候,他们的位移差不就是倒数第k个了嘛 💥 💥 💥
总结
在本篇文章中
-
寻找链表的中间结点: 用快慢指针的速度差解决中点问题的理解
-
判断链表是否带环: 因为环,快慢直接总会一点一点相遇的快慢指针的熟悉
-
返回链表倒数第k个节点: 更扩展了,快慢指针也不一定先一起走,也有可能快指针先走,慢指针再跟着的思想
如果觉得小编写的还不错的咱可支持 三连 下 (定有回访哦) , 不妥当的咱请评论区 指正
希望我的文章能给各位宝子们带来哪怕一点点的收获就是 小编创作 的最大 动力 💖 💖 💖
这篇关于天下三分明月夜,独有快慢指针法(链表面试题篇)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!