Reverse a Linked List (Recursive and Iterative)

Problem: Given the head of a singly linked list, reverse the list and return the new head. Implement it both recursively and iteratively.

Constraints: Number of nodes up to 5000.

Example: [1,2,3,4,5] -> [5,4,3,2,1].

Approach: Iterative: maintain prev/curr pointers, repeatedly redirect curr.next to prev while advancing both, O(n) time O(1) space. Recursive: reverse the rest of the list first, then fix the pointer of the current node's next to point back, O(n) time O(n) space (call stack).