Problem Statement

In a TATA Elxsi embedded software module, a singly linked list of event nodes must be reversed before downstream processing. Given the head of a singly linked list, reverse the list and return the new head.

Formal Specification

Implement a function that takes head, the first node of a singly linked list, or null if the list is empty.

• Input: head where each node has fields val and next
• Output: The new head of the reversed linked list

You must reverse the list by changing node pointers, not by copying values into another structure.

Examples

Example 1 Input: head = [1, 2, 3, 4, 5] Output: [5, 4, 3, 2, 1] Explanation: Each node's next pointer is reversed, so the tail becomes the new head.

Example 2 Input: head = [7, 9] Output: [9, 7] Explanation: The second node points to the first, and the first becomes the tail.

Constraints

• The number of nodes is in the range [0, 5000]
• -5000 <= Node.val <= 5000
• Use pointer manipulation to reverse the list
• Aim for O(n) time and O(1) extra space