Reversing a Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2] Output: [2,1]

Example 3:

Input: head = [] Output: []

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

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)