环形链表【手绘漫画】面试必考之双指针（LeetCode 141）

本文主要是介绍环形链表【手绘漫画】面试必考之双指针（LeetCode 141），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

文章目录

图解算法与数据结构
- 1、前言
- 2、实例
- 3、正文
- 4、代码

图解算法与数据结构

1、前言

今天开始的是双指针！

下面一起来看看吧！！！
在这里插入图片描述
让我们从一个经典问题开始：

环形链表进阶版【手绘漫画】面试必考之双指针（LeetCode 142）

上次讲了进阶版的，你会发现普通版本太easy了~

还是来看题吧！
在这里插入图片描述

2、实例

LeetCode 142，一个求证链表中有没有环的题。
在这里插入图片描述

3、正文

一起来看一下：

两种情况：
1. 第一种情况：不出意外，fast 每轮再多走 1 步（这才是名副其实的快指针~），最终两个指针一定会相遇，返回 true；
在这里插入图片描述
2. 第二种情况：fast 走到链表末端，下一节点为空，说明链表无环，直接 break，返回 false（如果存在环，两个指针必然会相遇，追击问题，fast 速度是 slow 的二倍~）；

妙啊！！！

4、代码

/*** 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) {if(head==nullptr) return false;auto fast=head,slow=head;while(fast){fast=fast->next;slow=slow->next;if(fast) fast=fast->next;else break;if(fast==slow) return true;}return false;}
};