Reverse a linked list
A linked list is a chain of nodes. Each node is a ListNode with two fields: val, its value, and next, the node after it (None after the last node). You get head, the first node of a list, or None if the list is empty.
Turn the list around, so its values read from last to first, and return its new first node. For an empty list, return None. The tests read the values of the list you return. The classic answer reuses the given nodes and changes only their next links.
Examples write a linked list as the list of its values: [3, 8, 5, 1] means 3 → 8 → 5 → 1, and [] is an empty list.
head = [3, 8, 5, 1]Output[1, 5, 8, 3]The last node, 1, is now the head, and the old head, 3, is now last.
head = [6, 2]Output[2, 6]head = []Output[]An empty list stays empty: return None.
0 ≤ number of nodes ≤ 5,000
-5,000 ≤ node value ≤ 5,000
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.