Given the head of a linked list, reverse the list and return the new head of the reversed list.

The linked list is represented by a sequence of ListNodes, where each node points to the next node in the sequence, or null if it is the last node.

A ListNode has the following interface:

interface ListNode {
  val: number;
  next: ListNode | null;
}

Input

• head: ListNode | null: Head of the linked list, or null if the list is empty. Examples display each linked list as an array of values within the list

For an empty list, return null.

Input: list = [1,2,3,4,5]
Output: [5,4,3,2,1]
Explanation: The input list [1, 2, 3, 4, 5] creates a linked list that, when reversed, produces [5, 4, 3, 2, 1].

Input: list = []
Output: []
Explanation: The input list is empty, so the reversed linked list is also empty.

Constraints

• 0 <= Number of nodes <= 1,000
• -1,000 <= ListNode.val <= 1,000