Reverse a singly linked list iteratively. Explain the pointers.

Answer

• Keep prev = None and curr = head.
• Loop: save nxt = curr.next, point curr.next = prev, then move prev = curr, curr = nxt.
• When curr is None, prev is the new head.
• O(n) time, O(1) memory. A recursive version uses O(n) stack.

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

Key terms

• Linked list
• Time complexity
• Space complexity
• Two pointers
• Recursion
• Base case