305. Find the Middle Node of a Linked List

Given the head of a singly linked list, return the middle node of the list.

If there are two middle nodes (even length), return the second middle node.

Use the slow/fast pointer technique for O(n) time and O(1) space.

Input: Head of a singly linked list.

Output: The middle node (return the node itself; output its value as integer for checking).

Examples

Input: [1,2,3,4,5]
Output: 3
Explanation: Slow starts at 1, Fast starts at 1.
Step 1: slow=2, fast=3.
Step 2: slow=3, fast=5.
fast.next==NULL → stop. Middle = node(3), value=3.

Input: [1,2,3,4,5,6]
Output: 4
Explanation: Step 1: slow=2, fast=3. Step 2: slow=3, fast=5. Step 3: slow=4, fast=NULL.
fast==NULL → stop. Second middle = node(4), value=4.

Input: [1,2]
Output: 2
Explanation: Two nodes: slow starts at 1. Step 1: slow=2, fast=NULL. Return node(2), value=2.

Constraints

• 1 <= number of nodes <= 10^5
• -10^9 <= Node.val <= 10^9

Asked by