Reverse Linked List

1. One-Liner

Reverse a singly linked list by rewiring next pointers so traversal order flips—iteratively with prev/cur pointers.

2. The Problem It Solves

Needed for palindrome checks (reverse half), stack-free undo of order, and many follow-up problems.

3. The Core Idea

Carry prev (starts null) and walk cur; save next, point cur→prev, slide forward—classic three-pointer dance.

4. How It Works (Step-by-Step)

Step	Action
1	prev=null, cur=head
2	While cur: nxt=cur.next; cur.next=prev
3	prev=cur; cur=nxt
4	Return prev as new head

5. Dry Run Example

1→2→3: after loop prev points to new head 3→2→1→null.

6. Key Properties

Property	Detail
In-place	O(1) extra for pointers
Stable	N/A—order reversed
Recursion	O(n) stack possible

7. Where It Is Used

Domain / System	Use
Editors	Undo lists
Kernels	mbuf chains
Interviews	Palindrome, add numbers

8. Interview Tips

Handle empty and single node. Mention recursive version if asked—same logic, implicit stack.

9. Comparison with Other Algorithms

Technique	Notes
Copy to array	O(n) space
Stack of nodes	Extra space
Doubly linked	Easier but different structure

10. Complexity


--	--
Time	O(n)
Space	O(1) iterative

Implementation Example (PYTHON)

def reverse_list(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev, cur = cur, nxt
    return prev