Double pointer of linked list (fast and slow pointer, sequential pointer, head and tail pointer)

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.

At this time, the typical linked list ring problem , The way to solve the circular problem of linked lists is to use fast and slow pointers .

Don't misunderstand the fast and slow pointer , The speed pointer is not the front and back pointer , The fast and slow pointer means a person who walks fast , One walks slowly , For example, one step at a time , Two steps at a time .

In this case , If there is a ring , Then take two steps （ In front of ）, We will definitely catch up with each other in the ring （ Walk in the back ）, I really want to run on the playground , The fast runner will always surpass the slow one again .

So set two speed pointers , We can judge whether it is a ring by seeing whether it will meet .

     public boolean hasCycle(ListNode head) {
    
         if(head==null)return false;
        ListNode slowNode=head;
        ListNode fastNode=head;
        
        while(fastNode!=null&&fastNode.next!=null){
     // In fact, this has to be written on the basis of understanding , Because if there is no ring , that fast Take two steps at a time , It is possible to walk a distance null For two steps , It's also possible to walk a distance null For one step , So I while Nei must write like that 
            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;

	// The principle of this question is  
	 Use the speed pointer , Two steps at a time , Slow pointer one step at a time , So the fast pointer travels twice as far as the slow pointer ,
	 So when the fast pointer traverses to the end of the linked list , The slow pointer points to the intermediate node （ From the solution of Li Kou problem ）
    }

At the beginning, I combined this problem with The speed pointer above is confused .
This problem should be called sequential pointer, which is more accurate , Let a pointer go first , Stop when certain conditions are met . Then two pointers go together .

Allied And this question

The idea is exactly the same

Another is the enhanced version of the above circular linked list , Not only to find out whether the linked list has rings , Also find out the starting point of the ring .

The idea is to find the place where the fast and slow pointers meet first , Then put a node at the place where they meet and at the head of the chain , Went together , Where the two nodes meet
Is the starting point of the ring . Specific derivation can refer to Code Capriccio solution

The code is as follows ：

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