Problem

At Stripe, a service stores event sequences as singly linked lists. Write a function that reverses a singly linked list and returns the new head.

Formal Specification

You are given the head of a singly linked list. Each node contains a value and a pointer next to the next node, or null if it is the last node. Return the head of the reversed list.

Implement the function so that it updates pointers in-place rather than creating a second list.

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]
• Output: [7]
• Explanation: A single-node list is already reversed.

Example 3

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

Constraints

• The number of nodes is in the range [0, 5000]
• -10^4 <= node.val <= 10^4
• The list is singly linked
• Aim for O(n) time and O(1) extra space