Newest first in a chat thread

Scenario

Kestrel Chat keeps the messages of a thread as a chain of nodes, from the oldest message to the newest. Each node holds a message id and a pointer to the next message.

A new "newest first" view shows the same thread from the other end. The team does not want a copy of the thread for it. The view turns the chain around in place and reuses the same nodes, so a long thread costs no extra memory. A thread holds up to 100,000 messages.

Your task

Write newest_first(head).

head is the first node of the thread, the oldest message, or null when the thread is empty. Each node's val is a message id.
Reverse the chain in place, and return the new head: the node of the newest message.
Do not create new nodes. Every node keeps its value; only the next pointers change.

The tests give head as the list of values from the head, and read your answer the same way.

Examples

Example 1 (traced)#

text2 lines

Input:  head = [101, 102, 103, 104]
Output: [104, 103, 102, 101]

Step	prev	curr	next (saved)	Arrow turned	Chain reversed so far
start	null	101			none
1	null	101	102	101 now points at null	101
2	101	102	103	102 now points at 101	102 → 101
3	102	103	104	103 now points at 102	103 → 102 → 101
4	103	104	null	104 now points at 103	104 → 103 → 102 → 101
end	104	null			return prev, the node of 104

Each step turns one arrow. When curr reaches null, prev holds the newest message.

Example 2#

text2 lines

Input:  head = []
Output: []

An empty thread has no nodes. The loop never runs, and prev is still null.

Example 3#

text2 lines

Input:  head = [7]
Output: [7]

One message points at null before and after. It is its own head.

Constraints

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

What does n ≤ 10^5 tell you?

One walk down the chain is 10^5 hops, far inside the time limit. A plan that walks from the head again for every position is about n^2 / 2 hops: 5 × 10^9 at this size, which is too slow.

So visit each node once. The scenario also asks for no copy, which rules out reading the values into an array and writing them back. You need O(1) extra memory: a few pointers.

Scenario

Kestrel Chat keeps the messages of a thread as a chain of nodes, from the oldest message to the newest. Each node holds a message id and a pointer to the next message.

Your task

Write newest_first(head).

head is the first node of the thread, the oldest message, or null when the thread is empty. Each node's val is a message id.
Reverse the chain in place, and return the new head: the node of the newest message.
Do not create new nodes. Every node keeps its value; only the next pointers change.

The tests give head as the list of values from the head, and read your answer the same way.

Examples

Example 1 (traced)#

text2 lines

Input:  head = [101, 102, 103, 104]
Output: [104, 103, 102, 101]

Step	prev	curr	next (saved)	Arrow turned	Chain reversed so far
start	null	101			none
1	null	101	102	101 now points at null	101
2	101	102	103	102 now points at 101	102 → 101
3	102	103	104	103 now points at 102	103 → 102 → 101
4	103	104	null	104 now points at 103	104 → 103 → 102 → 101
end	104	null			return prev, the node of 104

Each step turns one arrow. When curr reaches null, prev holds the newest message.

Example 2#

text2 lines

Input:  head = []
Output: []

An empty thread has no nodes. The loop never runs, and prev is still null.

Example 3#

text2 lines

Input:  head = [7]
Output: [7]

One message points at null before and after. It is its own head.

Constraints

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

What does n ≤ 10^5 tell you?

One walk down the chain is 10^5 hops, far inside the time limit. A plan that walks from the head again for every position is about n^2 / 2 hops: 5 × 10^9 at this size, which is too slow.

So visit each node once. The scenario also asks for no copy, which rules out reading the values into an array and writing them back. You need O(1) extra memory: a few pointers.