387. Middle of the Linked List

Given a non-empty singly linked list, return the value of the middle node. If there are two middle nodes (even length), return the value of the second one.

Input: An array of node values.

Output: Integer — the middle node's value.

Examples

Input: [1,2,3,4,5]
Output: 3
Explanation: Middle node is 3.

Input: [1,2,3,4,5,6]
Output: 4
Explanation: Second middle for even length.

Input: [1]
Output: 1
Explanation: Single node.

Constraints

• 1<=n<=10^4
• -10^9<=value<=10^9

Asked by