教你如何轻松学会Java快慢指针法
一、什么是快慢指针?
快慢指针就是定义两根指针,移动的速度一快一慢,以此来制造出自己想要的差值。这个差值可以让我们找到链表上相应的节点。
那快慢指针可以解决哪些实际问题呢,接下来我们一起看看吧!
二、使用快慢指针来找到链表的中点
1.首先我们设置两个指针slow和fast,这2个指针的初始位置相同,都指向链表的头结点,然后slow指针每次移动一步,fast指针每次移动两步;
2.如果链表中节点个数为偶数时,当快指针无法继续移动时,慢指针刚好指向中点;如果链表中节点个数为奇数时,当快指针走完,慢指针指向中点的前一个节点。
public ListNode reverseStore(ListNode head) { // 初始化,让快指针和慢指针都处于链表的头部 ListNode slow=head; ListNode fast=head; while(fast!=null&&fast.next!=null){//如果快指针并且下一个不为空 fast=fast.next.next;//快指针移动两个 slow=slow.next;//慢指针移动一个 } return slow; }
三、利用快慢指针来判断链表中是否有环
问题描述: 给定一个链表,判断链表中是否有环。
以下两种情况都属于链表中存在环,“0”字型和“6”字型
这个时候我们的解决方案就是利用“快慢指针”, 慢指针针每次走一步,快指针每次走两步,如果相遇就说明有环,如果有一个为空说明没有环。代码比较简单 (在代码下面会专门讲解思路的,放心!)
public boolean hasCycle(ListNode head) { if (head == null) return false; //快慢两个指针,初始时都指向链表的头结点 ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { //慢指针每次走一步 slow = slow.next; //快指针每次走两步 fast = fast.next.next; //如果相遇,说明有环,直接返回true if (slow == fast) return true; } //否则就是没环 return false; }
到这里大家可能就有疑问了,为什么快慢指针就一定能判断是否有环。我们可以这样来思考一下,假如有环,那么快慢指针最终都会走到环上,假如环的长度是m,快慢指针最近的间距是n,如下图中所示
下面说的两点相距是指 “快指针还需要多远可以再次追到慢指针”
快指针每次走两步,慢指针每次走一步,所以每走一次快慢指针的间距就要缩小一步,在图一中当走n次的时候就会相遇,在图二中当走m-n次的时候就会相遇。这样就解释清楚了读者的疑问了。
四、删除链表的倒数第n个节点
问题描述:删除倒数第n个节点,那就等于是要我们先找出待删除元素前一个元素,也就是第n-1个节点。聪明的你肯定发现了,我们又把这个问题转化为找链表上的某个节点的问题了,这是快慢指针最擅长的场景。
思路很简单,我们一开始就让fast指针比slow指针快n+1个元素,接下来,两个指针都是一步一步来往下走。那么当fast指针走完时,slow指针就刚刚好停留在第(n-1)个元素上。
//删除链表倒数第n个节点 public ListNode removeBackEndNode(ListNode head, int n) { if (head == null || head.next == null) { return null; } ListNode dummyHead = new ListNode(-1); dummyHead.next = head; //初始时让快慢指针都指向链表的头部 ListNode slow = dummyHead; ListNode fast = dummyHead; for (int i = 0; i < n + 1; i++) { fast = fast.next; } while (fast != null) { slow = slow.next; fast = fast.next; } slow.next = slow.next.next; //为了解决断链问题 return dummyHead.next; }
五、判断是否是回文链表
快指针每次前进两个单位,慢指针每次前进一个单位并修改其next节点指向前一个节点,所以当快指针到达链表末尾的时候(空节点或空节点的前一个节点),慢指针刚好在中间,如下图所示
此时慢指针继续向后走,同时开辟一个新节点往前走,看下图
判断链表中点前后是否相同,达到判断回文串的目的,如下图所示
代码如下:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public boolean isPalindrome(ListNode head) { if(head == null || head.next == null){ return true; } ListNode pre = null;//指向前一个节点的指针 ListNode slow = head;//慢指针 ListNode fast = head;//快指针 while(fast!=null&&fast.next!=null){ fast = fast.next.next; ListNode next = slow.next; slow.next = pre;//修改慢指针走过的节点指向前一个节点 pre = slow; slow = next; } if(fast != null){ slow = slow.next; //当长度为奇数是,慢指针需要再走一个单位 } while(pre!=null) { //判断是否为回文串 if(pre.val!=slow.val){ return false; } pre = pre.next; slow = slow.next; } return true; } }
到此这篇关于教你如何轻松学会Java快慢指针法的文章就介绍到这了,更多相关Java快慢指针法内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20- 这篇文章主要介绍了Java线程池中的各个参数如何合理设置操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-06-19
- 在Java中,我们可以利用多线程来最大化地压榨CPU多核计算的能力,下面这篇文章主要给大家介绍了关于java中多线程与线程池基本使用的相关资料,需要的朋友可以参考下...2021-09-13