Reverse Linked List

Reversing a linked list means changing the direction of the next pointers so that the last node becomes the head and the original head becomes the tail.

Iterative Approach

Traverse the list while keeping track of the previous, current, and next nodes, reversing the next pointer at each step.

def reverse_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev  # new head

Recursive Approach

Recursively reverse the rest of the list, then fix the pointers on the way back up the call stack.

def reverse_list_recursive(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

Complexity

Applications

• Palindrome checking on linked lists.
• Undo functionality where operations need to be replayed in reverse.
• A common building block in problems like reversing sub-portions of a list or reversing in groups of k.