Leetcode simple question sharing (20)

876. The middle node of a list

This is a simple linked list problem , The core problem is to find the central point .

Because this linked list is not a two-way linked list , So we can't simply consider the idea of double pointer reverse traversal . So a fast and slow pointer is a good way .

The concept of fast and slow pointer is that the slow pointer takes one step at a time , Then he goes n The result of this time is n;

Two steps at a time , go n The result of this time is 2n.

Then when the fast pointer goes to the end of the linked list When , That is, the value of the fast pointer is null or the next one of the fast pointer is null . This is the node pointed by the slow pointer, which is the central node .

The code is as follows ：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        // Slow pointer 
        ListNode slowPointer = head;
        // Quick pointer 
        ListNode fastPointer = head;
        // Jump out of the loop when the fast pointer is empty or the next node of the fast pointer is empty 
        while(fastPointer!=null && fastPointer.next!=null){
            // Slow pointer one step 
            slowPointer = slowPointer.next;
            // Let's go two steps 
            fastPointer = fastPointer.next.next;
        }
        // Return slow pointer 
        return slowPointer;
    }
}