Reverse Linked List

Given the head of a singly linked list, reverse the list in place and return the new head. This is the first problem to use the judge's typed ListNode support: head is a real linked-list node chain built from the JSON test fixture, not a plain array — your function must walk .val/.next pointers like a genuine LeetCode submission, and whatever node chain you return is serialized back to an array for grading.

Input / output

• Input: head: ListNode (JSON test fixture is an array of node values, e.g. [1, 2, 3] means 1 -> 2 -> 3 -> null)
• Output: ListNode — the head of the reversed list (serialized the same way)

Examples

1. head = [1, 2, 3, 4, 5] returns [5, 4, 3, 2, 1].
2. head = [1, 2] returns [2, 1].
3. head = [] returns [].

Constraints

• 0 <= number of nodes <= 5,000
• -100,000 <= node value <= 100,000
• Reverse the list in place; do not just reverse a copied array of values.

Follow-up Can you reverse the list both iteratively (O(1) extra space) and recursively (O(n) call-stack space), and explain the tradeoff an interviewer would expect you to name?