Reverse a Linked List (Iterative & Recursive)

Problem: Reverse a singly linked list.

Constraints: Implement the solution both iteratively and recursively.

Example: Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULL

Approach:

• Iterative: maintain three pointers (prev, curr, next). Walk the list once, at each node save next, point curr.next to prev, then advance prev and curr. O(n) time, O(1) space.
• Recursive: recurse to the last node, then on the way back set curr.next.next = curr and curr.next = null, returning the new head from the base case. O(n) time, O(n) recursion stack space.