Given the head of a singly linked list, reverse the list without modifing the values of the nodes (modify only their pointers).

Function Signature:

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

def reverse_linked_list(head: ListNode) -> ListNode:
    """
    Reverse the linked list.

    Parameters:
    - head: The head of the linked list.

    Returns:
    - ListNode: The head of the reversed linked list.
    """
    # Your code here

Example:

# 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")

Note:

  • You are not allowed to modify the values of the nodes, only their pointers.

Instructions:

  • Write the reverse_linked_list function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊