Given the head of a singly linked list, return the value at the middle node. If the list has an even number of nodes, return the value at the second middle node.
Input
head: the head of a singly linked list (passed as an array of node values)
Output
The value stored at the middle node.
Examples
Example 1
Inputhead = [1, 2, 3]
Output2
Example 2
Inputhead = [1]
Output1
Constraints
The list contains at least one node.