环形链表[简单]

优质博文：IT-BLOG-CN

一、题目

给你一个链表的头节点head，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递。仅仅是为了标识链表的实际情况。

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

二、代码

public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;// 空链表、单节点链表一定不会有环while (fast != null && fast.next != null) {fast = fast.next.next; // 快指针，一次移动两步slow = slow.next;      // 慢指针，一次移动一步// 不要比较value，对象可能是个空的if (fast == slow) {   // 快慢指针相遇，表明有环return true;}}return false; // 正常走到链表末尾，表明没有环}
}

三、思路

可以使用快慢指针法，分别定义fast和slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点， 如果 fast和slow指针在途中相遇，说明这个链表有环。

为什么fast走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢？
首先第一点：fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。
那么来看一下，为什么fast指针和slow指针一定会相遇呢？
可以画一个环，然后让fast指针在任意一个节点开始追赶slow指针。