ProblemThe input values represent a singly linked list in head-to-tail order.…
2024
Problem
The input values represent a singly linked list in head-to-tail order. Reverse the list and print its values from the new head to the tail.
Input format
The first integer is n, the number of nodes. The next n integers are the node values in head-to-tail order.
Output format
Print the values of the reversed list from the new head to the tail, separated by spaces.
Examples
Example 1 — Input: n = 4; values: 1 2 3 4
Output: 4 3 2 1. Reversing every next pointer makes 4 the new head.
Example 2 — Input: n = 5; values: 2 7 10 9 8
Output: 8 9 10 7 2.
Example 3 — Input: n = 1; value: 8
Output: 8. A one-node list is unchanged.
Constraints
1 ≤ n ≤ 30,000
1 ≤ node value ≤ 105
Attempted by 7 students.
Show answer & explanation
Concept
A singly linked list is reversed by redirecting each node’s next pointer toward its predecessor. Three references preserve the changing boundary: prev is the reversed prefix, current is the next node to process, and next saves the unreversed suffix before a link is changed.
Each node is processed once, so the iterative algorithm uses O(n) time and O(1) auxiliary space.
Application
Initialize
prev = nullandcurrent = head.While
currentis not null, savenext = current.nextso the remaining list is not lost.Set
current.next = prev, then advanceprev = currentandcurrent = next.For 1 → 2 → 3 → 4, the reversed prefix grows as 1, then 2 → 1, then 3 → 2 → 1, and finally 4 → 3 → 2 → 1.
Cross-check
After the loop, current is null and prev points to the former tail. Traversing from prev visits every original node exactly once in reverse order, and the former head points to null.
Therefore, return prev as the new head.