You are given a singly linked list. Write a function to reverse the linked list.

Function Signature:

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

def reverse_linked_list(head: ListNode) -> ListNode:
    """
    Reverse the given linked list and return the new head.

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

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

Example:

# Input: 1 -> 2 -> 3 -> 4 -> 5
# Output: 5 -> 4 -> 3 -> 2 -> 1

# Input: 1
# Output: 1

Note:

  • You may not modify the values in the nodes, only nodes itself may be changed.
  • Your solution should have O(1) space complexity.

Instructions:

  • Write the reverse_linked_list function to solve the problem.
  • Implement your solution in Python.
  • Feel free to use helper functions if needed.
  • 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 😊