Reverse Linked List [Solution]

Here’s a Python implementation of the reverse_linked_list function:

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

def reverse_linked_list(head: ListNode) -> ListNode:
    # Base case: if the list is empty or has only one node, return the head
    if not head or not head.next:
        return head

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

    # Adjust the pointers to reverse the current node
    head.next.next = head
    head.next = None

    return reversed_head

# Example usage:
# Create a 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)

# Reverse the linked list recursively
result = reverse_linked_list(head)

# Display the reversed linked list: 5 -> 4 -> 3 -> 2 -> 1
current = result
while current:
    print(current.val, end=" -> ")
    current = current.next
print("None")

This solution recursively reverses the linked list by first reversing the rest of the list and then adjusting the pointers to reverse the current node.

Time Complexity:

The time complexity is O(n), where n is the number of nodes in the linked list.

Space Complexity:

The space complexity is O(n) due to the recursion stack.