双指针技巧还可以分为两类，一类是「快慢指针」，另一类是「左右指针」。 前者解决主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或者字符串）中的问题，比如二分查找。
环形链表
给定一个链表，判断链表中是否有环。
![]()
题目分析
相信对于 JS 中的 JSON.stringify() 方法大家都用过，主要用于将 JS 对象 转换为 JSON 字符串。基本使用如下：
var car = {
name: '环形链表',
age: 123,
}
var str = JSON.stringify(car);
console.log(str)
// {"name":"环形链表","age":123}
大家想一下，如果是自己实现这样的一个函数，我们需要处理什么样的特殊情况？对，就是循环引用。因为对于循环引用，我们很难通过 JSON 的结构将其进行展示！
![]()
比如下面：
var ls = {
name: '李四',
age: 27
}
var zs = {
name: '张三',
age: 12
}
ls.father = zs;
zs.father = ls;
console.log(zs)
console.log(JSON.stringify(zs))
![]()
所以我们可以通过 JSON.stringify() 的特性进行求解：
var hasCycle = function(head) {
try{
JSON.stringify(head)
}catch(e){
return true
}
return false
};
当然，这种解法并不是建议的标准题解！在此列出是为了拓宽思维！（大家如有兴趣，可以自己去看下JSON.stringify 内部的实现，是如何检测循环引用的。）
也是本题标准解法！
思路来源：先想象一下，两名运动员以不同速度在跑道上进行跑步会怎么样？
相遇！
好了，这道题你会了。
解题方法：通过使用具有 不同速度 的快、慢两个指针遍历链表，空间复杂度可以被降低至 O(1)。慢指针每次移动一步，而快指针每次移动两步。
假设链表为![]()
其步骤如下：
![]()
分析完毕，直接上代码：
var ls = {
name: '李四',
age: 3
}
var zs = {
name: '张三',
age: 2
}
var ww = {
name: '王五',
age: 4
}
var zl = {
name: '赵六',
age: 0
}
ls.next = zs;
zs.next = ww;
ww.next = zl;
zl.next = ls;
console.log(zs);
function hasCycle(ListNode) {
if (!ListNode) return;
let fast = ListNode.next; // 快指针图1
while (fast && ListNode && fast.next) {
if (fast == ListNode) {
return true;
}
ListNode = ListNode.next;
fast = fast.next.next
}
return false;
}
console.log(hasCycle(zs));
zl.next = {};
console.log(hasCycle(zs));
这里我们要特别说明一下，为什么慢指针的步长设置为 1 ，而快指针步长设置为 2 。
首先，慢指针步长为 1，很容易理解，因为我们需要让慢指针步行至每一个元素。而快指针步长为 2 ，通俗点可以理解为他们的相对速度只差 1，快的只能一个一个格子的去追慢的，必然在一个格子相遇。
如果没看懂，我们来分析：在快的快追上慢的时，他们之间一定是只差 1 个或者 2 个格子。如果落后 1 个，那么下一次就追上了。如果落后 2 个，那么下一次就落后 1 个，再下一次就能追上！
如下图：
![]()
所以我们的快指针的步长可以设置为 2 。
原文参考
-
小浩算法：https://www.geekxh.com/1.1.%E9%93%BE%E8%A1%A8%E7%B3%BB%E5%88%97/103.html
