当前位置:网站首页>链表之双指针(快慢指针,先后指针,首尾指针)
链表之双指针(快慢指针,先后指针,首尾指针)
2022-07-05 22:27:00 【CodeStars码星人】
141. Linked List Cycle](https://leetcode.cn/problems/linked-list-cycle/)
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
这时典型的链表环形问题,链表环形问题的做法就是快慢指针。
快慢指针不要理解错了,快慢指针不是前后指针,快慢指针的意思是一个走得快,一个走得慢,比如说一个一次走一步,一个走两步。
这样的话,如果出现环形的话,那么走两步的(在前面的),肯定会在环内追上走一步的(走在后面),就好想操场跑步,跑得快的始终会再次超过跑得慢的那个。
所以就设置两个快慢指针,看是否会相遇就可以判断是否成环了。
public boolean hasCycle(ListNode head) {
if(head==null)return false;
ListNode slowNode=head;
ListNode fastNode=head;
while(fastNode!=null&&fastNode.next!=null){
//其实这个还是得在理解的基础上才写得出来的,因为如果是没环的,那么fast每次走两步,有可能走到距离null为两步,也可能走到距离null为一步,所以就while内得那么写
slowNode=slowNode.next;
fastNode=fastNode.next.next;
if(slowNode==fastNode)return true;
}
return false;
}
876. Middle of the Linked List
class Solution {
public ListNode middleNode(ListNode head) {
if(head==null)return null;
ListNode slow=head;
ListNode fast=head;
while(fast.next!=null&&fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
}
if(fast.next==null)return slow;
if(fast.next.next==null)return slow.next;
return head;
//此题原理就是
利用快慢指针,快指针每次走两步,慢指针每次走一步,所以快指针走的距离为慢指针的两倍,
故当快指针遍历到链表末尾时,慢指针指向记为中间节点(来自力扣题解)
}
一开始就是将这道题和 上面的快慢指针混淆了。
这个题应该叫做先后指针比较准确,让一个指针先走,到符合一定条件时停下来。然后再两个指针一起走。
类似的 还有这道题
思路是一模一样的
另外就是上面循环链表的加强版,不仅要找到链表是否有环,还要找出环的起点。
思路就是先找快慢指针相遇的地方,然后在相遇的地方和链头开始放一个节点,一起走,两个节点相遇的地方
就是环的起点。具体推导可以参考代码随想录的解法
代码如下:
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null)return null;
ListNode result=head;
ListNode slow=head;
ListNode fast=head;
int count=0;
while(fast.next!=null&&fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
if(slow==fast) break;
}
if(fast.next==null||fast.next.next==null) return null;
while(result!=slow){
result=result.next;
slow=slow.next;
}
return result;
}
}
边栏推荐
- 解决thinkphp启动时“No input file specified”的问题
- 记录几个常见问题(202207)
- 如何快速体验OneOS
- Unique occurrence times of leetcode simple questions
- Promql demo service
- BFC block level formatting context
- 谷歌地图案例
- Understand the basic concept of datastore in Android kotlin and why SharedPreferences should be stopped in Android
- Damn, window in ie open()
- Search: Future Vision (moving sword)
猜你喜欢
[groovy] groovy dynamic language features (automatic type inference of function arguments in groovy | precautions for function dynamic parameters)
The countdown to the launch of metaverse ape is hot
Metasploit(msf)利用ms17_010(永恒之蓝)出现Encoding::UndefinedConversionError问题
opencv 判断点在多边形内外
How can Bluetooth in notebook computer be used to connect headphones
Metaverse ape received $3.5 million in seed round financing from negentropy capital
Business learning of mall commodity module
ESP32 hosted
Interprocess communication in the "Chris Richardson microservice series" microservice architecture
Overview of database recovery
随机推荐
Opencv judgment points are inside and outside the polygon
Metaverse Ape上线倒计时,推荐活动火爆进行
Metaverse ape received $3.5 million in seed round financing from negentropy capital
The code generator has deoptimised the styling of xx/typescript. js as it exceeds the max of 500kb
二叉树(三)——堆排序优化、TOP K问题
Postman core function analysis - parameterization and test report
Concurrency control of performance tuning methodology
2022软件测试工程师涨薪攻略,3年如何达到30K
U盘的文件无法删除文件怎么办?Win11无法删除U盘文件解决教程
database mirroring
Common interview questions of JVM manufacturers
Shelved in TortoiseSVN- Shelve in TortoiseSVN?
2022-07-05:给定一个数组,想随时查询任何范围上的最大值。 如果只是根据初始数组建立、并且以后没有修改, 那么RMQ方法比线段树方法好实现,时间复杂度O(N*logN),额外空间复杂度O(N*
Leetcode simple question: the minimum cost of buying candy at a discount
[agc009e] eternal average - conclusion, DP
Granularity of blocking of concurrency control
实战:fabric 用户证书吊销操作流程
[error record] file search strategy in groovy project (src/main/groovy/script.groovy needs to be used in the main function | groovy script directly uses the relative path of code)
点到直线的距离直线的交点及夹角
Leetcode simple question: find the nearest point with the same X or Y coordinate