Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the new head.
Constraints:
- The number of nodes in the list is in the range
[0, 1000]. - Node values are in the range
[-1000, 1000].
Example 1:
Input: head = [1, 2, 3, 4, 5] Output: [5, 4, 3, 2, 1]
Example 2:
Input: head = [] Output: []
Recommended time and space complexity
You should aim for a solution with O(n) time complexity and O(1) space complexity for the iterative approach or O(n) for the recursive approach, where n is the length of the list.
Hint 1
A brute force approach would be to create a new list and copy elements in reverse order. This would be an O(n) time and O(n) space solution. Can you think of a more efficient approach?
Hint 2
Can you reverse the list by changing the links between nodes without using additional memory?
Hint 3
Use three pointers: `prev`, `curr`, and `next`. Move them through the list, changing the direction of the links.