Reverse a Linked List

You are given head, the first node of a singly linked list. Reverse the list so that the last node becomes the first and every node's next pointer leads to the node that came before it.

Return the head of the reversed list.

Linked List Encoding

Your function receives head as a ListNode (or null for the empty list) and returns the head of the reversed list. The node type is provided for you, with val and next fields; you may relink the existing nodes in place.

The examples below write a list as the array of its values in order, so [1,2,3] is the list 1 -> 2 -> 3. That is only how lists are displayed; the encoding and decoding are done for you.

Examples

Example 1

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Explanation: The list 1 -> 2 -> 3 -> 4 -> 5 becomes 5 -> 4 -> 3 -> 2 -> 1.

Example 2

Input: head = [1,2]
Output: [2,1]

Example 3

Input: head = []
Output: []
Explanation: The empty list reverses to itself.