当前位置:网站首页>鏈錶之雙指針(快慢指針,先後指針,首尾指針)
鏈錶之雙指針(快慢指針,先後指針,首尾指針)
2022-07-05 22:28: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;
}
}
边栏推荐
- APK加固技术的演变,APK加固技术和不足之处
- Storage optimization of performance tuning methodology
- 如何開發引入小程序插件
- [error record] groovy function parameter dynamic type error (guess: groovy.lang.missingmethodexception: no signature of method)
- Pl/sql basic syntax
- Metaverse ape ape community was invited to attend the 2022 Guangdong Hong Kong Macao Great Bay metauniverse and Web3.0 theme summit to share the evolution of ape community civilization from technology
- Go语言学习教程(十五)
- Business learning of mall commodity module
- boundary IoU 的计算方式
- Pl/sql basic case
猜你喜欢
Win11运行cmd提示“请求的操作需要提升”的解决方法
Kubernetes Administrator certification (CKA) exam notes (IV)
元宇宙中的三大“派系”
MySQL服务莫名宕机的解决方案
Metaverse Ape上线倒计时,推荐活动火爆进行
Cobaltstrike builds an intranet tunnel
The countdown to the launch of metaverse ape is hot
點到直線的距離直線的交點及夾角
Distance from point to line intersection and included angle of line
Pl/sql basic case
随机推荐
119. Pascal‘s Triangle II. Sol
QT creator 7-cmake update
Request preview display of binary data and Base64 format data
[groovy] groovy dynamic language features (automatic type inference of function arguments in groovy | precautions for function dynamic parameters)
Distance from point to line intersection and included angle of line
Draw a red lantern with MATLAB
[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)
thinkphp5.1跨域问题解决
科技云报道荣膺全球云计算大会“云鼎奖”2013-2022十周年特别贡献奖
What changes has Web3 brought to the Internet?
Three "factions" in the metauniverse
航海日答题小程序之航海知识竞赛初赛
Text组件新增内容通过tag_config设置前景色、背景色
实战:fabric 用户证书吊销操作流程
Server optimization of performance tuning methodology
2022 Software Test Engineer salary increase strategy, how to reach 30K in three years
Database tuning solution
U盘的文件无法删除文件怎么办?Win11无法删除U盘文件解决教程
如何快速体验OneOS
Solve the problem of "no input file specified" when ThinkPHP starts