Introduce

The single linked list is defined as follows ：

class ListNode {
    
    int val;
    ListNode next;
    
    ListNode() {
    
    }
    
    ListNode(int val) {
    
        this.val = val;
    }

    ListNode(int val, ListNode next) {
    
        this.val = val;
        this.next = next;
    }
}

Given a single chain table , How to quickly find the midpoint of a single linked list ?
In the normal way , You need to traverse the single linked list twice , First traverse the linked list to get the length of the linked list , Then take half according to the length of the linked list and traverse the single linked list again to get the midpoint of the single linked list .
Usable fast （fast）、 slow （slow） Two pointers traverse the single linked list to complete , Quick pointer fast Two steps at a time , Slow pointer one step at a time , Start traversing the linked list , The cycle condition is while（fast != null && fast.next != null）

• If the length of the single linked list is odd , Then at the end of the cycle ,slow The pointer just points to the midpoint of the linked list
• If the length of the single linked list is even , Then at the end of the cycle ,slow The pointer points to the right node of the middle two nodes

The implementation is as follows ：

ListNode getMidNode(ListNode head) {
     //  Get the midpoint of the linked list 
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
    
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
}

An application

LeetCode141 Circular list

analysis ： Set speed pointer , The fast pointer moves multiple nodes at a time , Slow pointer moves one node at a time , If there is a ring , Fast pointer will “ Catch up ” The node indicated by the slow pointer .

class Solution {
    
    public boolean hasCycle(ListNode head) {
    
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
    
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow) {
    
                return true;
            }
        }
        return false;
    }
}