Double pointeur de liste liée (pointeur rapide et lent, pointeur séquentiel, pointeur de tête et de queue)

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.

C'est le problème typique de l'anneau de liste , L'approche du problème de l'anneau de liste est un pointeur rapide et lent .

Les pointeurs rapides et lents ne doivent pas être mal compris , Les pointeurs rapides et lents ne sont pas des pointeurs avant et arrière , Les pointeurs rapides et lents signifient une marche rapide , Une marche lente , Comme marcher un pas à la fois ,Deux pas chacun..

Dans ce cas, Si un anneau apparaît , Alors, deux pas （Devant）, Je suis sûr qu'un pas dans le ring （ Marche derrière ）, Je veux courir sur le terrain de jeu , Celui qui court vite dépassera toujours celui qui court lentement .

Alors réglez deux pointeurs rapides et lents , Voir si vous vous rencontrerez peut déterminer si c'est un anneau .

     public boolean hasCycle(ListNode head) {
    
         if(head==null)return false;
        ListNode slowNode=head;
        ListNode fastNode=head;
        
        while(fastNode!=null&&fastNode.next!=null){
     // En fait, ça doit être écrit sur la base de la compréhension , Parce que si c'est sans anneau ,AlorsfastDeux pas à la fois, Il est possible de marcher jusqu'à la distance nullPour deux pas, Ou peut - être à distance null Pour une étape ,C'est tout.while Ça doit être écrit comme ça 
            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;

	// Le principe de cette question est  
	Avec un pointeur rapide et lent,Le pointeur rapide marche deux pas à la fois,Le pointeur lent fait un pas à la fois, Donc le pointeur rapide marche deux fois plus loin que le pointeur lent ,
	 Donc quand le pointeur rapide traverse la fin de la liste , Pointeur lent pointant vers le noeud intermédiaire （De la solution de la boucle de force）
    }

Au début, j'ai comparé cette question à Le pointeur de vitesse ci - dessus est confus .
Ce problème devrait être appelé pointeur séquentiel plus précis , Laissez un pointeur aller en premier , Arrêtez - vous quand certaines conditions sont remplies . Et puis deux autres pointeurs ensemble .

Similaire Et cette question

L'idée est exactement la même

L'autre est une version améliorée de la liste de liens en boucle ci - dessus , Il ne suffit pas de trouver si la liste a des anneaux , Et trouver le point de départ de l'anneau .

L'idée est de trouver d'abord où les pointeurs rapides et lents se rencontrent , Ensuite, placez un noeud au point de rencontre et au début de la chaîne ,On y va ensemble., Où les deux noeuds se rencontrent
C'est le point de départ de l'anneau . Pour plus de détails, voir La solution à l'enregistrement aléatoire de code

Les codes sont les suivants:：

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