图解算法与数据结构

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;}
};

如果有幸帮到你，请帮我点个【赞】，给个【关注】！如果能顺带【评论】给个鼓励，我将不胜感激。

如果想要更多的资源，欢迎关注 @我是管小亮，文字强迫症MAX~