快慢指针一般都初始化指向链表的头结点 head，前进时快指针 fast 在前，慢指针 slow 在后，巧妙解决一些链表中的问题。
“快”与“慢”的差别可能是俩指针的速率，也可能是速率一致但是快指针比慢指针先走几步

判定链表是否有环

经典解法就是用两个指针，一个每次前进两步（快指针），一个每次前进一步（慢指针）。
在遍历的过程中，

如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；
如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环

# leetcode 141
function hasCycle(head){
    if(head == null || head.next == null) {
        return false;
    }
    let slow = head,
        fast = head;
    while(fast&&fast.next){
        fast = fast.next.next;
        slow = slow.next
        if(fast == slow){
            return true
        }
    }
    return false
}

总结：这里快慢指针的运用，主要体现在每次步数的倍数差（速率差），且俩指针在一个环里运动，2倍速的指针总会与一倍速的指针相遇。

求链表中环的起始位置

已知链表中含有环，返回这个环的起始位置

设快指针每次走两步，慢指针每次走一步
这题我们运用快慢指针的路程差，我们已知在一个环里，快慢指针总会相遇，那么第一次相遇的时候快指针与慢指针的行程差是多少呢？是一个环的长度

设相遇点距环的起点的距离为 m，那么环的起点距头结点 head 的距离为 k - m，即慢指针从head出发行走k-m即可到达我们所求的环起点！
那么k-m怎么估量呢？巧的是这里有个转换，k是第一次相遇时slow指针走的步数，同时也是快指针与慢指针的行程差，即绿色圆环。从快指针的角度看，在环里从第一次相遇的地方再走k-m步亦可回到环起点。

所以，思路就转换为: 当相遇之后再走k-m步即可回到环起点，即相遇之后让慢指针从head出发走k-m步，快指针在相遇的地方就地出发，以同样的速率向前进，两指针再次相遇的时候就是环起点。（k-m只是个概数，实际操作让两指针再次相遇即可)

总结：
1、快慢指针各自以二倍速、一倍速的步伐前进，直至第一次相遇
2、第一次相遇后，慢指针回到head起点，同时快指针保持在相遇位置
3、快慢指针同步以一倍速前进，直至再次相遇，此时相遇的位置即为起始位置

# leetcode 142
function detectCycle(head) {
    if (head==null) return null;
    let slow = fast = head;
    // 求出第一次相遇的位置 同判断链表是否有环一致
    while(fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
        if (slow === fast) {
            // 将slow指针指回head
            slow = head;
            // 开始第二次相遇 此时的相遇点即为环起始
            while (slow!==fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    // 直接while跳出的 即无环情况
    return null;
};

求链表中间点

求链表中间的结点，同样利用快慢指针速率倍差导致的路程倍差，快指针二倍速，慢指针一倍速，当快指针走完全程时，慢指针正好在路程的一半

# leetcode 876
var middleNode = function(head) {
    let fast = slow = head;
    while(fast&&fast.next){
        fast = fast.next.next
        slow = slow.next
    }
    return slow;
};

值得注意的是：当链表的长度是奇数时，slow 恰巧停在中点位置；如果长度是偶数，slow 最终的位置是中间偏右

扩展：
寻找链表中点的一个重要作用是对链表进行归并排序。
回想数组的归并排序：求中点索引递归地把数组二分，最后合并两个有序数组。
对于链表，合并两个有序链表是很简单的，难点就在于二分

而使用快慢指针可以轻松找到链表的中点

求链表的倒数第k个数

利用快慢指针的路程差，这里快指针和慢指针速率一致，但是快指针比慢指针先走k步。然后两者齐头并进，当快指针到达终点时，慢指针此时与快指针相差k步，即在倒数第k个结点（假设k不超过链长）

# leetcode 19 
function getLastkNode(head, n) {
    let fast = slow = head;

    while(n--) {
        fast = fast.next;
    }

    while(fast) {
        fast = fast.next;
        slow = slow.next;
    }

    return slow;
 }

求两个无环单链表交点

两个链表的遍历分别由两个遍历指针控制，他们都会访问交点
如果他们在访问到交点的时候是同时发生的就好了！这样根据相遇就可以得到交点
但是链表长度不一致，不能保证同时出发到达交点时是同时到达的（即从head到出发点长度一致）
=>
所以问题很自然的转换为—长链表的遍历指针先走len1-len2步，然后两指针同时同速率前进，这样即能在交点相遇

# leetcode 160
function getIntersectionNode(headA,headB){
    let p1 = headA,
        p2 = headB;
    while(p1&&p2){
        p1 = p1.next;
        p2 = p2.next
    }

    // 其中一方 弹尽粮绝,那么剩下的那一方还有的长度就是他们的长度之差
    // 那就继续迭代引用p，同时head指向的真实链表搭个顺风车
    while(p1!=null){// headA长一点
        p1 = p1.next;
        headA =  headA.next;
    }

    while(p2!=null){
        p2 = p2.next;
        headB = headB.next;
    }
    // 开始一起走了，走在准备相遇的路上
    while(headA&&headB){
        if(headA==headB){
            return headA
        }
        headA = headA.next;
        headB = headB.next;
    }
    return null
}

最后

参考资料
双指针技巧汇总

扩展
双指针之左右指针技巧

🤔数据结构与算法

【技巧】快慢指针

判定链表是否有环

求链表中环的起始位置

求链表中间点

求链表的倒数第k个数

求两个无环单链表交点

最后