Reverse a Linked List

Problem Reverse a singly linked list in place and return the new head. Implement it both iteratively and recursively.

Input / Output

• Input: head — pointer to the first node of a singly linked list (may be null).
• Output: pointer to the head of the reversed list.

Constraints

• 0 <= number of nodes <= 5000; node values fit in a 32-bit integer.
• The iterative version must use O(1) extra space; relink existing nodes rather than reallocating.

Example

• 1 -> 2 -> 3 -> 4 -> 5 -> NULL → 5 -> 4 -> 3 -> 2 -> 1 -> NULL.
• Edge cases: empty list and single node must both return without dereferencing null.