A
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.
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.
Example 1
head = [1, 2, 3, 4, 5][5, 4, 3, 2, 1]next pointer is reversed, so the tail becomes the new head.Example 2
head = [7][7]Example 3
head = [][][0, 5000]-10^4 <= node.val <= 10^4O(n) time and O(1) extra spacehead = [1, 2, 3, 4, 5]Output[5, 4, 3, 2, 1]WhyThe links are reversed one by one, so the original tail becomes the new head.head = [7]Output[7]WhyA single node has no links to change, so the result is the same list.head = []Output[]WhyThere are no nodes to reverse, so the function returns an empty list.The number of nodes is in the range [0, 5000]-10^4 <= node.val <= 10^4The input is a singly linked listThe list should be reversed in-placedef reverse_linked_list(head):