The middle of a reply chain

Scenario

On Kestrel Feed, a long reply chain under a post opens with a "jump to the middle" button. The replies are stored as a chain of nodes, oldest first. Each node holds a reply id and a pointer to the next reply. The chain does not store its length.

The button shows the replies from the middle reply onwards. When the chain has an even number of replies, it has two middles, and the product rule picks the second one. A chain holds 1 to 100,000 replies.

Your task

Write preview_from(head).

head is the first node of the reply chain. It is never null. Each node's val is a reply id.
With n replies, the middle reply is the one at position n / 2, rounded down, counting from 0 at the head. For an even n, that is the second of the two middles.
Return the node of the middle reply. Do not change the chain.

The tests read your answer as the list of values from the node you return to the end of the chain.

Examples

Example 1 (traced)#

text2 lines

Input:  head = [31, 45, 12, 78, 50]
Output: [12, 78, 50]

Round	slow	fast	Can fast move two more?
start	31	31	yes: 45 and 12 follow
1	45	12	yes: 78 and 50 follow
2	12	50	no: 50 is the last reply
end	12	50	return slow: position 2 = 5 / 2, rounded down

fast moves two replies for every one that slow moves. When fast stops at the end, slow has gone half as far.

Example 2#

text2 lines

Input:  head = [31, 45, 12, 78, 50, 66]
Output: [78, 50, 66]

Six replies have two middles, 12 and 78. In round 3, slow reaches 78 and fast moves past the end. The answer is the second middle, at position 3.

Example 3#

text2 lines

Input:  head = [9]
Output: [9]

Constraints

1 ≤ number of nodes ≤ 10^5
1 ≤ node.val ≤ 10^9

What does n ≤ 10^5 tell you?

Any plan that walks the chain a fixed number of times is fast: two walks of 10^5 hops each fit easily. A plan that walks again from the head for every reply is about n^2 / 2 hops, 5 × 10^9 at this size, which is too slow.

Counting first and then walking to position n / 2 is correct and O(n). The two-cursor walk below does the same in one pass, which matters when the chain is still growing or is read as a stream.

Scenario

Your task

Write preview_from(head).

head is the first node of the reply chain. It is never null. Each node's val is a reply id.
With n replies, the middle reply is the one at position n / 2, rounded down, counting from 0 at the head. For an even n, that is the second of the two middles.
Return the node of the middle reply. Do not change the chain.

The tests read your answer as the list of values from the node you return to the end of the chain.

Examples

Example 1 (traced)#

text2 lines

Input:  head = [31, 45, 12, 78, 50]
Output: [12, 78, 50]

Round	slow	fast	Can fast move two more?
start	31	31	yes: 45 and 12 follow
1	45	12	yes: 78 and 50 follow
2	12	50	no: 50 is the last reply
end	12	50	return slow: position 2 = 5 / 2, rounded down

fast moves two replies for every one that slow moves. When fast stops at the end, slow has gone half as far.

Example 2#

text2 lines

Input:  head = [31, 45, 12, 78, 50, 66]
Output: [78, 50, 66]

Six replies have two middles, 12 and 78. In round 3, slow reaches 78 and fast moves past the end. The answer is the second middle, at position 3.

Example 3#

text2 lines

Input:  head = [9]
Output: [9]

Constraints

1 ≤ number of nodes ≤ 10^5
1 ≤ node.val ≤ 10^9

What does n ≤ 10^5 tell you?

Counting first and then walking to position n / 2 is correct and O(n). The two-cursor walk below does the same in one pass, which matters when the chain is still growing or is read as a stream.