图解算法与数据结构

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