Linked Lists Fast and slow pointers
288. Middle of the Linked List
You are given head, the first node of a singly linked list. Return the middle node of the list.
A singly linked list is a chain of nodes. Each node holds a value and a pointer to the next node, and the last node's pointer is null. The middle node has as many nodes before it as after it. A list with an even number of nodes has two middle nodes; return the second of them.
The examples write a list as its values from the head on, so head = [4,1,6] is the list 4 → 1 → 6. The
output shows the node you return the same way, as the list from that node on.
Example 1
Input: head = [5, 3, 8, 1, 9, 4, 7]
[1,9,4,7]Explanation: The list has seven nodes. The fourth node holds 1, and it has three nodes before it and three after it, so the answer is the list from that node on.
Example 2
Input: head = [10, 20, 30, 40]
[30,40]Explanation: Four nodes have two middle nodes, the ones holding 20 and 30. The answer is the second of them.
Example 3
Input: head = [-6]
[-6]Explanation: A list of one node has nothing before or after its only node, so that node is the middle.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.