当前位置:网站首页>Double pointer of linked list (fast and slow pointer, sequential pointer, head and tail pointer)
Double pointer of linked list (fast and slow pointer, sequential pointer, head and tail pointer)
2022-07-05 22:28:00 【Codestars 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.
At this time, the typical linked list ring problem , The way to solve the circular problem of linked lists is to use fast and slow pointers .
Don't misunderstand the fast and slow pointer , The speed pointer is not the front and back pointer , The fast and slow pointer means a person who walks fast , One walks slowly , For example, one step at a time , Two steps at a time .
In this case , If there is a ring , Then take two steps ( In front of ), We will definitely catch up with each other in the ring ( Walk in the back ), I really want to run on the playground , The fast runner will always surpass the slow one again .
So set two speed pointers , We can judge whether it is a ring by seeing whether it will meet .
public boolean hasCycle(ListNode head) {
if(head==null)return false;
ListNode slowNode=head;
ListNode fastNode=head;
while(fastNode!=null&&fastNode.next!=null){
// In fact, this has to be written on the basis of understanding , Because if there is no ring , that fast Take two steps at a time , It is possible to walk a distance null For two steps , It's also possible to walk a distance null For one step , So I while Nei must write like that
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;
// The principle of this question is
Use the speed pointer , Two steps at a time , Slow pointer one step at a time , So the fast pointer travels twice as far as the slow pointer ,
So when the fast pointer traverses to the end of the linked list , The slow pointer points to the intermediate node ( From the solution of Li Kou problem )
}
At the beginning, I combined this problem with The speed pointer above is confused .
This problem should be called sequential pointer, which is more accurate , Let a pointer go first , Stop when certain conditions are met . Then two pointers go together .
Allied And this question
The idea is exactly the same
Another is the enhanced version of the above circular linked list , Not only to find out whether the linked list has rings , Also find out the starting point of the ring .
The idea is to find the place where the fast and slow pointers meet first , Then put a node at the place where they meet and at the head of the chain , Went together , Where the two nodes meet
Is the starting point of the ring . Specific derivation can refer to Code Capriccio solution
The code is as follows :
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加固技术和不足之处
- Cobaltstrike builds an intranet tunnel
- Overriding equals() & hashCode() in sub classes … considering super fields
- 笔记本电脑蓝牙怎么用来连接耳机
- Leetcode simple question: the minimum cost of buying candy at a discount
- Distance from point to line intersection and included angle of line
- 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
- Binary tree (II) -- code implementation of heap
- The new content of the text component can be added through the tag_ Config set foreground and background colors
- Business learning of mall commodity module
猜你喜欢
Serializability of concurrent scheduling
What about data leakage? " Watson k'7 moves to eliminate security threats
Oracle advanced query
Livelocks and deadlocks of concurrency control
Cobaltstrike builds an intranet tunnel
Summary of concurrency control
Performance monitoring of database tuning solutions
What if win11 is missing a DLL file? Win11 system cannot find DLL file repair method
How to quickly experience oneos
Blocking protocol for concurrency control
随机推荐
Performance testing of software testing
IIC bus realizes client device
GWT module may need to be (RE) compiled reduce - GWT module may need to be (RE) compiled reduce
Opencv judgment points are inside and outside the polygon
Go language learning tutorial (XV)
Index optimization of performance tuning methodology
科技云报道:算力网络,还需跨越几道坎?
MCU case -int0 and INT1 interrupt count
Matlab draws a cute fat doll
How can easycvr cluster deployment solve the massive video access and concurrency requirements in the project?
Technology cloud report won the special contribution award for the 10th anniversary of 2013-2022 of the "cloud Ding Award" of the global cloud computing conference
Distance entre les points et les lignes
344. Reverse String. Sol
The difference between MVVM and MVC
[agc009e] eternal average - conclusion, DP
A trip to Suzhou during the Dragon Boat Festival holiday
What changes has Web3 brought to the Internet?
Solutions for unexplained downtime of MySQL services
分布式解决方案之TCC
What if win11 is missing a DLL file? Win11 system cannot find DLL file repair method