鏈錶之雙指針（快慢指針，先後指針，首尾指針）

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;
    }
}