Solutions

# Reverse pointers.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# Iteration: O(n) time, O(1) space
def reverse_list(head: ListNode) -> ListNode:
    prev = None
    curr = head
    while curr:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    return prev


# Recursion: O(n) time, O(n) space
def reverse_list(head: ListNode) -> ListNode:
    if not head:
        return None
    
    newhead = head
    if head.next:
        newhead = reverse_list(head.next)
        head.next.next = head # reverse the next link of next node

    head.next = None
    return newhead