Reverse a Linked List — Interview Guide

• Maintain a prev pointer (initially null) and a current pointer.
• At each step, save next, point current's next at prev, then advance prev and current.
• The recursive version reverses the rest first, then points the next node back at the head.

def reverse(head):
    prev = None
    while head:
        nxt = head.next
        head.next = prev
        prev = head
        head = nxt
    return prev

def reverse(head):
    if not head or not head.next:
        return head
    new_head = reverse(head.next)
    head.next.next = head
    head.next = None
    return new_head