Problem Statement

Given the head of a singly linked list, reverse the list, and return the reversed list.

Additional information

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Example 1:

Input: head = [1, 2, 3, 4, 5]

Output: [5, 4, 3, 2, 1]

Example 2:

Input: head = [1, 2]

Output: [2, 1]

Example 3:

Input: head = []

Output: []

Brute Force (Store and Reverse)

Intuition

The simplest approach is to traverse the linked list and store all node values in an array. Then, reverse the array and create a new linked list from it. This is straightforward but uses extra space.

Algorithm

1. Traverse the list and store all values in an array.
2. Reverse the array.
3. Create a new linked list from the reversed array.
4. Return the new head.

def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]:
    values = []
    curr = head
    while curr:
        values.append(curr.val)
        curr = curr.next
    
    values.reverse()
    dummy = ListNode(0)
    curr = dummy
    for val in values:
        curr.next = ListNode(val)
        curr = curr.next
    return dummy.next

Time & Space Complexity

• Time complexity: O(n)

• Reason: We traverse the list once to collect values, then once more to build the new list.

• Space complexity: O(n)

• Reason: We store all node values in an array.

Iterative (Optimal)

Intuition

We can reverse the list in place without extra space by changing the direction of the pointers as we traverse. We use three pointers: prev (initially None), curr (starts at head), and nxt (saves the next node before we break the link). For each node, we redirect its next pointer to point backwards to prev, then advance all three pointers forward.

Algorithm

1. Initialize prev = None and curr = head.
2. While curr is not None:

• Save the next node: nxt = curr.next.
• Reverse the pointer: curr.next = prev.
• Advance prev to curr.
• Advance curr to nxt.

3. When the loop ends, prev points to the new head (the last node of the original list). Return prev.

def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]:
    prev = None
    curr = head
    
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
        
    return prev

Time & Space Complexity

• Time complexity: O(n)

• Reason: We visit every node exactly once.

• Space complexity: O(1)

• Reason: We only use three pointers (prev, curr, nxt), regardless of the list size.