206. Reverse Linked List

Problem Statement in English

You are given the head of a singly linked list. Reverse the list, and return the reversed list.

Approach

There are two approaches to solve this problem: iterative and recursive.

The recursive approach is more elegant and easier to understand, but it uses more space due to the call stack. You make a recursive call for each node in the list and pass it the previous node. When you reach the end of the list, you return the last node, which becomes the new head of the reversed list. As the recursion unwinds, you set the next pointer of each node to point to its previous node.

The iterative approach is more efficient in terms of space but is more complex to implement and understand. You maintain three pointers: previous, current, and next. You iterate through the list, reversing the next pointer of each node to point to its previous node. When you reach the end of the list, the previous pointer will be pointing to the new head of the reversed list.

For this approach, I think reading the code is going to be more helpful than reading the explanation.

Solution in Python

• Recursive Approach, $O(n)$ time and $O(n)$ space

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head: return None
        
        def rev(node, prev):
            next = node.next
            node.next = prev

            if next:
                return rev(next, node)
            return node
        
        return rev(head, None)

• Iterative Approach, $O(n)$ time and $O(1)$ space

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        temp = head
        prev = None

        while temp:
            next = temp.next
            temp.next = prev
            prev = temp

            temp = next
        
        return prev

And we are done.