Given the head of a singly linked list, reverse the list, and return the reversed list. Example 1: Input: Output: head = [1,2,3,4,5] [5,4,3,2,1] Example 2: Input: Output: head = [1,2] [2,1] Example 3: Input: Output: head = [] [] Constraints: The number of nodes in the list is the range [0, 5000]. -5000 <= Node.val <= 5000 Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both? Solution Approach 1: Iterative def reverse_list(head: ListNode) -> ListNode: prev = None current = head while current: next = current.next current.next = prev prev = current current = next return prev https://youtu.be/LcKcMDP6WwU?embedable=true Space complexity: O(1) Time complexity: O(n) Approach 2: Recursive def reverse_list(head: ListNode) -> ListNode: if not head or not head.next: return head new_head = reverse_list(head.next) head.next.next = head head.next = None return new_head Space complexity: O(n) Time complexity: O(n)
