leetCode The first 876 topic The middle node of a list
link ：https://leetcode-cn.com/problems/middle-of-the-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 .
Of course, the general method is to calculate the length of the linked list first , Then calculate the position of the intermediate node , Then return this node to .
This calculates the length of the loop once , Find the node and cycle once , Time complexity is also increasing O(n) Level .
But setting up the speed pointer can reduce the cycle to one .
The speed pointer is set to head It's about ,fast In steps of 2,slow In steps of 1, because fast The velocity is slow Twice as many , So when fast At the end of the linked list ,slow Just in the middle of the linked list .
## python3
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
slow = head
fast = head
while fast != None and fast.next != None:
slow = slow.next
fast = fast.next.next
return slow
