Reverse Linked List [LC#206]

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

Iterative approach

     ┌────┐    ┌────┐    ┌────┐
 <-- │prev│    │curr│--> │next│-->
     └────┘    └────┘    └────┘
     ┌────┐    ┌────┐    ┌────┐
 <-- │prev│ <--│curr│    │next│-->
     └────┘    └────┘    └────┘
     ┌────┐    ┌────┐    ┌────┐
 <-- │    │ <--│prev│    │next│-->
     └────┘    └────┘    └────┘
     ┌────┐    ┌────┐    ┌────┐
 <-- │    │ <--│prev│    |curr│-->
     └────┘    └────┘    └────┘

def fn(head):
    curr = head
    prev = None
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

Time Complexity

• $T(n) = O(n)$
• $S(n) = O(1)$