Middle of the Linked List

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

Example

Input: 1 2 3 4 5 Output: 3

Approach

The same fast/slow pointer technique as cycle detection: advance slow by one and fast by two. By the time fast reaches the end, slow is exactly at the middle — one pass, no need to count the length first.

Input format

Line 1: the list values, space-separated

Print the middle node's value.