2、环形链表

题目描述

环形链表

下面我们再来了解一种双指针，我们称之为快慢指针，顾名思义一个指针速度快，一个指针速度慢。

给定一个链表，判断链表中是否有环。pos 代表环的入口，若为-1，则代表无环。

如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。

题目解析

题目很容易理解，让我们判断链表中是否有环，我们只需通过我们的快慢指针即可，我们试想一下，如果链表中有环的话，一个速度快的指针和一个速度慢的指针在环中运动的话，若干圈后快指针肯定可以追上慢指针的。这是一定的。

好啦，做题思路已经有了，让我们一起看一下代码的执行过程吧。

动画模拟

代码

Java Code:

public class Solution {
    public boolean hasCycle(ListNode head) {
         ListNode fast = head;
         ListNode low = head;
         while (fast != null && fast.next != null) {
             fast = fast.next.next;
             low = low.next;
             if (fast == low) {
                 return true;
             }
         }
         return false;
    }
}

C++ Code:

class Solution {
public:
    bool hasCycle(ListNode *head) {
         ListNode * fast = head;
         ListNode * slow = head;
         while (fast != nullptr && fast->next != nullptr) {
             fast = fast->next->next;
             slow = slow->next;
             if (fast == slow) {
                 return true;
             }
         }
         return false;
    }
};