Reverse a Linked List

Problem: Reverse a singly linked list in place.

Constraints: Standard singly linked list, no auxiliary array/list allowed for an optimal in-place solution.

Example: 1->2->3->4->null becomes 4->3->2->1->null.

Approach: Iteratively walk the list keeping prev, curr, and next pointers; at each step set curr.next = prev, then advance prev = curr and curr = next. Continue until curr is null; prev is the new head. O(n) time, O(1) space. A recursive approach is also common (O(n) space for the call stack).