Given the head of a singly linked list, return its middle node. If there are two middle nodes, return the second one.
Lists are written as arrays in the examples, and the tests read the list from the node you return: [3, 4, 5] means you returned the node holding 3.
Examples
Example 1
- Input
- head = [1, 2, 3, 4, 5]
- Output
- [3, 4, 5]
- Why
- The middle node holds 3.
Example 2
- Input
- head = [1, 2, 3, 4, 5, 6]
- Output
- [4, 5, 6]
- Why
- There are two middle nodes, 3 and 4, so the answer is the second: 4.
Constraints
- The list has between
1and100nodes. 1 <= Node.val <= 100