环形链表
WangScaler: 一个用心创作的作者。声明：才疏学浅，如有错误，恳请指正。
题目
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
初次分析
遍历整个链表，同时记录每个节点是否被访问过，如果被访问过，则返回true。遍历结束如果没有发现被访问过的节点，则返回false。
这时候我们需要一个Hash表来存储每个节点访问的情况。我们能不能不额外的引入这个哈希呢？
继续分析
一般这种都是用双指针，那么我们这个题能不能用双指针？
我们用一个指针标记头指针的位置。如果是个环，那么另一个指针会回到头指针。但是答案却不是，因为
只有这种情况是可以的，但是
却不行，起初看题目有个pos,则认为头指针就是环形的起始节点，那么我标记头指针就能判断答案，后来仔细看了下题目，才知道pos是leecode用来标记答案的，跟我们没有关系，题目说明了评测系统内部使用。
这个题没想出解法，看了答案，使用了龟兔赛跑的思想。一个指针一个节点一个节点移动，另一个指针领先一步，两个节点两个节点的移动。
- 如果没有环，当快兔走到终点时，则认为没有环，false。
- 如果有环，那么跑到前边的兔子会从后边追上跑的慢的乌龟，true。
答案
public static boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}复杂度
时间复杂度: O(n)。
- 没有环时，快兔遍历1/2遍链表，结束。
- 有环时，最坏的情况也就是遍历次数的情况就是头节点就是环的一部分或者进入环时快指针是慢指针的next节点。此时两个指针几乎相差整个环的长度，每次遍历两个指针的距离减一。此时是遍历次数最多的情况也就是环的长度。
所以时间复杂度时O(n)。
- 空间复杂度: O(1),只需要两个快慢指针。
总结
上边的时间复杂度可能不好理解。画个图理解下吧。
情况一
- 初始时
- 一次循环之后
- 两次循环
- 三次循环，这时候黑色和红色重合，则认为是个环。
这是最好的情况
情况二
- 初始位置 距离黑色三个位置
- 一次循环 距离黑色两个位置
- 二次循环、距离黑色一个位置
- 三次循环 重合
这是最坏情况。
情况三
- 初始位置、距离黑色三个节点。
- 一次循环、距离黑色两个节点
- 二次循环、距离黑色一个节点
- 三次循环、结束
总结
时间复杂度取决于进入环时的两个快慢指针的位置。最好的情形就是情况一，遍历环前边的次数即可停止。最坏的情形就是情况二。可以看到黑色的球走过了所有的节点也就是O(n),所以最坏的时间复杂度是O(n)。
都来了，点个赞再走呗！关注WangScaler，祝你升职、加薪、不提桶！
