Find the intermediate node of the linked list

Fast and slow pointer method , Define a fast And a slow. Give Way fast The speed of slow Twice the speed , When fast To the last node of the linked list ,slow At the middle node , This is the time , Output slow.

Two ways of writing ：

The first one is ：

    public ListNode middleNode(){
    
        // When fast The speed of slow At twice the speed , When fast When you get to the last node ,slow In the middle .
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
    
            fast = fast.next.next;
            slow = slow.next;
        }
       return slow;
    }

The second kind ：

public ListNode middleNode(){
    
        // When fast The speed of slow At twice the speed , When fast When you get to the last node ,slow In the middle .
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null) {
    
            fast = fast.next.next;
            slow = slow.next;
        }
       return slow;
    }

The difference between the first and the second ：

• When the length of the linked list is odd , The results of the two calculations are the same
• When the linked list is even , There are two intermediate nodes , The intermediate nodes of the first calculation are two On the right the , The second way is On the left the .