Find the Middle of a Linked List

You are given a singly linked list. Your task is to find and return the value of the middle node of the list.

If the list contains an even number of nodes, there will be two middle nodes and you should return the value of the second middle node.

Note: The linked list will always contain at least one node.

The solution approach often uses the "fast and slow pointers" technique. In each step, the slow pointer moves one node while the fast pointer moves two nodes. When the fast pointer reaches the end of the list, the slow pointer will be at the middle node. In mathematical notation, if the list has \( n \) nodes, then after \( \lfloor \frac{n}{2} \rfloor \) steps the slow pointer points to the middle node.

inputFormat

The first line of input contains an integer \( n \) (1 \( \leq n \leq 10^5 \)), representing the number of nodes in the linked list.

The second line contains \( n \) space-separated integers, representing the node values in order from head to tail.

outputFormat

Output a single integer representing the value of the middle node of the linked list. If there are two middle nodes, output the value of the second one.

1
1

1