Middle of the Linked List

The problem. Given the head of a singly linked list, return the middle node. If there are two middle nodes (an even number of nodes), return the second one.

Example

Input:  head = [1, 2, 3, 4, 5]
Output: [3, 4, 5]        the middle node is 3

Input:  head = [1, 2, 3, 4, 5, 6]
Output: [4, 5, 6]        3 and 4 are both middles; return the second

With an array you'd just read arr[n / 2]. A linked list has no indexes and doesn't know its own length — that's what makes this interesting.