93. Find the Middle of a Linked List

A singly linked list has n node values. Print the value of its middle node. If n is even, print the value at 0-indexed position n/2 (the second of the two middle nodes).

Input: The first line contains an integer n. The second line contains n space-separated integers, the linked list's values in order. Output: Print a single integer - the value at the middle node.

1 <= n <= 10^5

Getting the EXACT tie-breaking convention right for even-length lists (landing on the second middle node here) is a small but important detail - different problems sometimes want the first middle instead, so always confirm which is expected.

Find the value sitting in the middle of a linked list, without knowing its length in advance. Brute force: Walk the list once to count its total length n, then walk it again from the head for n/2 steps to reach the middle - this works but requires TWO full passes, when a single pass suffices. Optimised: The slow/fast pointer technique finds the middle in a SINGLE pass: since the fast pointer covers ground twice as quickly, by the time it finishes the whole list, the slow pointer has covered exactly half the distance - no need to know the list's length ahead of time at all.

Traverse the linked list once, copying every node's value into an array as it's visited, then directly index into that array at position n/2 (0-indexed, per the problem's tie-breaking rule for even n) to read off the middle value. This is simple and correct, but it allocates memory proportional to the entire list just to answer what is really a positional question. Time: O(n) Space: O(n)

Make a first pass through the list purely to count the total number of nodes, n. Then make a second pass, walking from the head exactly n/2 steps forward (per the even-n tie-breaking rule), and return the value at that node. This needs only a couple of counters rather than storing every value, cutting memory to constant, at the cost of walking the list twice instead of once. Time: O(n) Space: O(1)

Use two pointers starting at the head: a slow pointer that advances one node per step and a fast pointer that advances two nodes per step. By the time the fast pointer reaches the end of the list (or falls one node short of it), the slow pointer is sitting exactly at the middle node, matching the required tie-breaking rule for even-length lists. This finds the middle in a single traversal of the list, needing neither a second pass nor any extra storage for values, which is the best possible given the list can only be walked forward. Time: O(n) Space: O(1)

1. Use two pointers, both starting at the head: a SLOW pointer moving one step at a time, and a FAST pointer moving two steps at a time. 2. When the fast pointer reaches the end of the list, the slow pointer is exactly at the middle. 3. For an even-length list, this lands on the SECOND of the two middle nodes, matching the required convention.

Time: O(n) - a single pass through the list. Space: O(1) - just two pointers, no extra storage.

n = 1 (the single node is the middle), and both even and odd n, since even n must print the second of the two middle nodes.

This slow/fast ('tortoise and hare') technique is foundational and reused constantly - be ready to instantly recognize it as the go-to approach whenever a linked-list problem needs the middle, a cycle check, or a specific position from the end.