Force buckle 5_ 876. Intermediate node of linked list

Given a header node as head The non empty single chain table of , Returns the middle node of the linked list .

If there are two intermediate nodes , Then return to the second intermediate node .

Example 1：

 Input ：[1,2,3,4,5]
 Output ： Nodes in this list  3 ( Serialization form ：[3,4,5])
 The returned node value is  3 . ( The evaluation system expresses the serialization of this node as follows  [3,4,5]).
 Be careful , We returned one  ListNode  Object of type  ans, such ：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5,  as well as  ans.next.next.next = NULL.

Example 2：

 Input ：[1,2,3,4,5,6]
 Output ： Nodes in this list  4 ( Serialization form ：[4,5,6])
 Because the list has two intermediate nodes , Values, respectively  3  and  4, Let's go back to the second node .

Tips ：

 The number of nodes in a given list is between  1  and  100  Between .

source ： Power button （LeetCode）

Java solution 1

A similar is used here C Double pointer method in language , Quick pointer Each move Two grid , Slow pointer Each move One grid Finally, when the fast pointer is finished, the slow pointer is half finished .

class Solution {
    
    public ListNode middleNode(ListNode head) {
    
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
    
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

Java solution 2

class Solution {
    
    public ListNode middleNode(ListNode head) {
    
        ListNode[] A = new ListNode[100];
        int t = 0;
        while (head != null) {
    
            A[t++] = head;
            head = head.next;
        }
        return A[t / 2];
    }
}

Python solution

there Python The traditional method is adopted , First save the linked list into the list , Get the intermediate elements of the list through the index .

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        A = [head]
        while A[-1].next:
            A.append(A[-1].next)
        return A[len(A) // 2]