You are given the head of a linked list. You have to return the value of the…

Concept: the slow-and-fast pointer (tortoise and hare) invariant. A singly linked list gives no random access and its length is not known in advance, so the middle node cannot be indexed directly. If two pointers start together at the head and one advances by one node per step while the other advances by two, then after k steps the slow pointer stands on node k and the fast pointer on node 2k, so the slow pointer is always exactly halfway along whatever the fast pointer has covered. The walk therefore has to stop the moment the fast pointer can no longer take a full two-node step, which happens in one of two ways: the fast pointer has moved past the last node and is NULL, or it is sitting on the last node and its next link is NULL. At that moment the slow pointer stands at the halfway node, reached in a single traversal and without ever counting the nodes.

Application: start slow = head and fast = head, then repeat, while fast is not NULL and fast->next is not NULL, moving slow forward by one node and fast forward by two nodes. When the loop ends, slow holds the required node and its data is the answer. This exact guard is what makes the walk stop on the second of the two middle nodes when the node count is even, which is the value this statement asks for.

Trace of the odd-length example 1->2->3->4->5:

1. Start: slow = 1, fast = 1.

2. First step: slow = 2, fast = 3.

3. Second step: slow = 3, fast = 5.

4. The guard now fails because fast->next is NULL, so the walk stops with slow on the node 3, which is the middle node and the answer.

Trace of the even-length example 2->4->6->7->5->1:

1. Start: slow = 2, fast = 2.

2. First step: slow = 4, fast = 6.

3. Second step: slow = 6, fast = 5.

4. Third step: slow = 7, fast = NULL.

5. The guard now fails because fast is NULL, so the walk stops with slow on the node 7, the second of the two middle nodes 6 and 7, which is the answer.

Cross-check with the counting method: traverse once to count n nodes, then walk floor(n / 2) further steps from the head, using integer division, which lands on the node at 0-based index floor(n / 2). For n = 5 that index is 2, the third node, whose value is 3; for n = 6 it is 3, the fourth node, whose value is 7. Both results agree with the single-pass walk above.

Points to keep in mind:

• The guard decides which middle you land on: looping while fast->next and fast->next->next are non-NULL stops one step earlier and leaves slow on the first middle node (the node 6 in the even-length example), which does not satisfy this statement.

• In this stdio version the list arrives as n followed by its n values, so the same invariant reduces to printing the value at 0-based index floor(n / 2); the two-pointer walk is the form used when a real head pointer is handed to a function instead.

• The single-pass walk costs O(n) time and O(1) extra space; the counting method uses the same extra space but needs two passes over the list.

• Because the constraints guarantee at least one node, the list is never empty, so slow always points at a real node when the loop ends.

Core of the single-pass walk:

slow = head;
fast = head;
while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
}
// slow now points at the required middle node; slow->data is the answer