A linked list is a chain of nodes. Each ListNode holds a value val and a reference next to the following node; the last node's next is None. There is no index: to reach the third node you must start at the head and follow next twice.
Given the head of a singly linked list, reverse the list and return the new head. The tests build the list from a Python list with list_to_linked and convert your result back with linked_to_list.
Examples
Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 5 -> 4 -> 3 -> 2 -> 1
Input: (empty list)
Output: (empty list)
Constraints
0 <= number of nodes <= 1000- Re-link the existing nodes; do not build a new list from the values
Goals
- Traverse a singly linked list by following next references
- Re-link nodes iteratively with prev and current references without losing the rest of the list