Reverse a linked list

Iterative Solution

def reverseList(head: ListNode) -> ListNode:
    prev = None
    current = head

    while current:
        next_node = current.next  # Save next
        current.next = prev       # Reverse pointer
        prev = current            # Move prev forward
        current = next_node       # Move current forward

    return prev

Recursive Solution

def reverseList(head: ListNode) -> ListNode:
    # Base case
    if not head or not head.next:
        return head

    # Recursively reverse the rest
    new_head = reverseList(head.next)

    # Reverse the pointer
    head.next.next = head
    head.next = None

    return new_head

Time: O(n) for both Space: O(1) iterative, O(n) recursive (call stack)