In a Google Cloud service, a lightweight in-memory queue may be represented as a singly linked list. Write a function that reverses a singly linked list and returns the new head.
Implement reverse_linked_list(head) where head is the first node of a singly linked list, or None for an empty list. Each node has two fields: val and next. Return the new head of the reversed list.
You must reverse the list in place by updating pointers, not by creating a second list of nodes.
Example 1
head = [1, 2, 3, 4, 5][5, 4, 3, 2, 1]next pointer is redirected so traversal starts from 5 and ends at 1.Example 2
head = [7][7]Example 3
head = [][]0 to 10^5 nodes.-10^9 <= Node.val <= 10^9O(1) extra space for the primary solution.next pointers.