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


def reverse_linked_list_recursive(head):
    # Base case: if the list is empty or has only one node
    if head is None or head.next is None:
        return head

    # Reverse the rest of the list recursively
    reversed_head = reverse_linked_list_recursive(head.next)

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

    # Return the new head of the reversed list
    return reversed_head


def print_linked_list(head):
    current = head
    while current is not None:
        print(current.val, end=" -> ")
        current = current.next
    print("None")


# Example usage:
# Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

print("Original linked list:")
print_linked_list(head)

# Reverse the linked list recursively
reversed_head = reverse_linked_list_recursive(head)

print("Reversed linked list:")
print_linked_list(reversed_head)

# Original linked list:
# 1 -> 2 -> 3 -> 4 -> 5 -> None
# Reversed linked list:
# 5 -> 4 -> 3 -> 2 -> 1 -> None

def reverse_linked_list_iteratively(head: Optional[ListNode]) -> Optional[ListNode]:
    if (head == None):
        return head
    nvar = head
    pvar = None
    while nvar != None:
        temp = nvar.next
        nvar.next = pvar
        pvar = nvar
        nvar = temp

    return pvar