Problem

In a Publicis Sapient engineering codebase, linked-list utilities may be used in low-level data transformations. Write a function that reverses a singly linked list and returns the new head.

Formal Specification

Implement a function reverse_linked_list(head) where:

• head is the first node of a singly linked list, or null for an empty list
• each node has two fields: val and next
• the function must return the new head of the reversed list

You must reverse the list by changing node pointers, not by creating a second list of copied nodes.

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 traversal starts from 5 and ends at 1.

Example 2 Input: head = [7] Output: [7] Explanation: A single-node list is already reversed.

Example 3 Input: head = [] Output: [] Explanation: An empty list remains empty.

Constraints

• 0 <= number of nodes <= 10^5
• -10^9 <= node.val <= 10^9
• The input list is singly linked
• Aim for one pass through the list
• Extra space should be constant for the iterative solution