当前位置:网站首页>Leetcode circular linked list (fast and slow pointer) code line by line interpretation
Leetcode circular linked list (fast and slow pointer) code line by line interpretation
2022-07-02 22:31:00 【ZibeSun】
Circular list
Preface
The judgment of circular linked list is a classical problem in algorithm learning , This article will explain and use the code to explain how to judge the circular linked list through the speed pointer .
subject
Give you a list of the head node head
, Judge whether there are links in the list .
If there is a node in the linked list , It can be done by continuously tracking next
The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , The evaluation system uses an integer pos
To indicate where the end of the list is connected to the list ( Index from 0 Start ).
Be careful :pos
Not passed as an argument . Just to identify the actual situation of the linked list .
If there are rings in the list , Then return to true
. otherwise , return false
.
Example :
Input :head = [3,2,0,-4], pos = 1
Output :true
explain : There is a link in the list , Its tail is connected to the second node .
Link to the original topic :https://leetcode-cn.com/problems/linked-list-cycle
solution - Speed pointer
Specific ideas : Create two pointers , A quick pointer , A slow pointer , Both pointers initially point to the chain header node . The fast pointer moves back two nodes at a time , The slow pointer moves back one node at a time . If the linked list has a ring , Then the fast and slow hands will meet . If the linked list has no ring , Then the fast pointer will go to the end of the linked list first .
Algorithm flow :
Special judgement : If the chain header node
head
Null pointer , Then return directly falseCreate a fast pointer , A slow pointer , Are initialized as chain header nodes
Traversing the linked list , Exit when the fast pointer is empty
The fast pointer goes back one node first , If the node is not empty , Then go back one node
Slow the pointer back one node
If the speed pointer is equal , And are not empty , Indicates that the speed pointer meets , The list has rings , return
true
If you traverse the linked list normally , It indicates that the linked list has no rings , return
false
Code implementation :
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
public:
bool hasCycle(ListNode *head) {
// Special judgement : If the chain header node head Null pointer , Then return directly false
if(head == NULL) return false;
// Create a fast pointer , Initialize to the chain header node
ListNode *fast = head;
// Create a slow pointer , Initialize to the chain header node
ListNode *slow = head;
// Traversing the linked list , Exit when the fast pointer is empty
while(fast != NULL){
// The fast pointer goes back one node first
fast = fast->next;
// If the node is not empty , Then go back one node
if(fast != NULL) fast = fast->next;
// Slow the pointer back one node
slow = slow->next;
// If you traverse the linked list normally , It indicates that the linked list has no rings , return false
if(fast == slow && fast != NULL) return true;
}
// If you traverse the linked list normally , It indicates that the linked list has no rings , return false
return false;
}
};
边栏推荐
- Unity3d learning notes 4 - create mesh advanced interface
- Market Research - current situation and future development trend of anti-counterfeiting label market
- Market Research - current situation and future development trend of sickle cell therapy Market
- An overview of the development of affective computing and understanding research
- 使用 EMQX Cloud 实现物联网设备一机一密验证
- Daily book CSO advanced road first exposed
- Bridge emqx cloud data to AWS IOT through the public network
- APP页面分享口令Rails实现
- SQL必需掌握的100个重要知识点:使用游标
- 【AUTOSAR-DCM】-4.3-UDS $22和$2E服务如何读取和写入NVM数据
猜你喜欢
"New programmer 003" was officially launched, and the cloud native and digital practical experience of 30+ companies such as Huawei and Alibaba
Hanoi Tower problem
《ActBERT》百度&悉尼科技大学提出ActBERT,学习全局局部视频文本表示,在五个视频-文本任务中有效!
[shutter] shutter application theme (themedata | dynamic modification theme)
How do I access the kubernetes API?
"New programmer 003" was officially launched, and the cloud native and digital practical experience of 30+ companies such as Huawei and Alibaba
Image segmentation using pixellib
It's not easy to say I love you | use the minimum web API to upload files (swagger support) # yyds dry inventory #
PIP audit: a powerful security vulnerability scanning tool
[001] [arm-cortex-m3/4] internal register
随机推荐
Sql service intercepts string
Unity3d learning notes 4 - create mesh advanced interface
Promise optimized callback hell
加了定位的文字如何水平垂直居中
《Just because》阅读感受
[QT] QT multithreading development - reentrancy and thread safety
App page sharing password rails implementation
C language, to achieve three chess games
What is it that makes you tremble? Those without fans can learn
Unity3D学习笔记4——创建Mesh高级接口
Using emqx cloud to realize one machine one secret verification of IOT devices
Ransack combined condition search implementation
如何访问kubernetes API?
2019 Nanchang (relive the classic)
Get off work on time! Episode 6 of Excel Collection - how to split and count document amounts
LandingSite eBand B1冒烟测试用例
[Jianzhi offer] 57 And are two numbers of S
Daily book CSO advanced road first exposed
《ActBERT》百度&悉尼科技大学提出ActBERT,学习全局局部视频文本表示,在五个视频-文本任务中有效!
Market Research - current market situation and future development trend of intravenous injection (IV) bottles