链表之双指针（快慢指针，先后指针，首尾指针）

141. Linked List Cycle](https://leetcode.cn/problems/linked-list-cycle/)

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

这时典型的链表环形问题，链表环形问题的做法就是快慢指针。

快慢指针不要理解错了，快慢指针不是前后指针，快慢指针的意思是一个走得快，一个走得慢，比如说一个一次走一步，一个走两步。

这样的话，如果出现环形的话，那么走两步的（在前面的），肯定会在环内追上走一步的（走在后面），就好想操场跑步，跑得快的始终会再次超过跑得慢的那个。

所以就设置两个快慢指针，看是否会相遇就可以判断是否成环了。

     public boolean hasCycle(ListNode head) {
    
         if(head==null)return false;
        ListNode slowNode=head;
        ListNode fastNode=head;
        
        while(fastNode!=null&&fastNode.next!=null){
     //其实这个还是得在理解的基础上才写得出来的，因为如果是没环的，那么fast每次走两步，有可能走到距离null为两步，也可能走到距离null为一步，所以就while内得那么写
            slowNode=slowNode.next;
            fastNode=fastNode.next.next;
            if(slowNode==fastNode)return true;
        }
return false;
    }

876. Middle of the Linked List

class Solution {
    
    public ListNode middleNode(ListNode head) {
    
        if(head==null)return null;
        
        ListNode slow=head;
        ListNode fast=head;

        while(fast.next!=null&&fast.next.next!=null){
    
            fast=fast.next.next;
            slow=slow.next;
        }

        if(fast.next==null)return slow;
        if(fast.next.next==null)return slow.next;
        return head;

	//此题原理就是 
	利用快慢指针，快指针每次走两步，慢指针每次走一步，所以快指针走的距离为慢指针的两倍，
	故当快指针遍历到链表末尾时，慢指针指向记为中间节点（来自力扣题解）
    }

一开始就是将这道题和 上面的快慢指针混淆了。
这个题应该叫做先后指针比较准确，让一个指针先走，到符合一定条件时停下来。然后再两个指针一起走。

类似的 还有这道题

思路是一模一样的

另外就是上面循环链表的加强版，不仅要找到链表是否有环，还要找出环的起点。

思路就是先找快慢指针相遇的地方，然后在相遇的地方和链头开始放一个节点，一起走，两个节点相遇的地方
就是环的起点。具体推导可以参考代码随想录的解法

代码如下：

public class Solution {
    
    public ListNode detectCycle(ListNode head) {
    
        if(head==null)return null;
        ListNode result=head;
        ListNode slow=head;
        ListNode fast=head;
        int count=0;
        while(fast.next!=null&&fast.next.next!=null){
    
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast) break;
        }        

        if(fast.next==null||fast.next.next==null) return null;
        while(result!=slow){
    
            result=result.next;
            slow=slow.next;
        }
        return result;
    }
}