89. Reverse a Linked List

A singly linked list is given as its n node values in order. Print the values in reverse order.

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 the values in reverse order, space-separated.

1 <= n <= 10^5

The recursive version of this (reverse the rest of the list first, then fix up the current node's links) is an elegant alternative worth knowing, though it uses O(n) stack space versus the iterative version's O(1).

Reverse the direction of a singly linked list, so the last node becomes the first. Brute force: Copy all values into an array, reverse the array, and build a brand new linked list from it - this works but allocates entirely new nodes when the existing ones can simply be relinked in place. Optimised: Relinking each node's OWN next pointer to point backward (rather than forward) as you walk the list once achieves the reversal using the EXISTING nodes - no new allocation needed, just careful pointer bookkeeping with the three-pointer technique.

Reverse the list iteratively using three pointers - prev (starting null), curr (starting at head), and a temporary next: in each step save curr.next, point curr.next back to prev, then advance both prev and curr forward by one; after the loop, prev is the new head. This achieves the same pointer rewiring as the recursive version but with a fixed, constant amount of extra memory instead of a call stack that grows with the list's length. Time: O(n) Space: O(1)

Traverse the linked list from head to tail, pushing every value onto an auxiliary stack as you go, then pop the stack and print each value. Because a stack is last-in-first-out, the values come out in the exact opposite order to how they were pushed, giving the reversed sequence without touching the original list's pointers at all. Time: O(n) Space: O(n)

Reverse the list recursively: recursively reverse everything starting at node.next first, then, on the way back up the call stack, set node.next.next = node and node.next = null, with the last node becoming the new head. This actually rewires the list's own pointers in place rather than just producing reversed output, at the cost of using the call stack as implicit storage proportional to the list's length. Time: O(n) Space: O(n)

1. Track three pointers as you walk the list: PREVIOUS (starts as null), CURRENT (starts at the head), and NEXT. 2. At each step, save current's next node, then point current's own next pointer BACKWARD to previous instead. 3. Advance previous and current forward by one, and repeat until current becomes null - previous is now the new head.

Time: O(n) - one single pass, relinking each node's next pointer exactly once. Space: O(1) extra space - the reversal happens entirely in place.

n = 1 (the list is unchanged), and n = 10^5 for performance.

This is one of THE most fundamental linked-list operations - be ready to write it flawlessly from memory, both iteratively (three pointers) and recursively, since it underlies many harder problems (palindrome check, add-1-to-number, and more).