Linked List Reversal changes the direction of all next pointers so the last node becomes the head and the original head becomes the tail. The iterative approach uses three pointers (prev, curr, next) and runs in O(n) time with O(1) space. A recursive approach uses the call stack for O(n) space.
Node* reverseList(Node* head) {
Node* prev = nullptr, *curr = head, *next = nullptr;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}Keep three pointers: prev (starts null), curr (starts at head), and next. On each step: save next=curr.next, point curr.next=prev, advance prev=curr, advance curr=next. When curr is null, prev is the new head.
We must save curr.next before overwriting it, otherwise we lose the rest of the list. The three pointers ensure we can advance forward while redirecting the current pointer backward.
Recursively reverse the rest of the list, then make head.next.next = head and head.next = null. Elegant but uses O(n) stack space — the iterative version is preferred in production.
Quiz coming soon for this algorithm.