The O(n) Club: Reverse Linked List — Because Losing Nodes Should Be Illegal

The O(n) Club: Reverse Linked List — Because Losing Nodes Should Be Illegal

⚡ TL;DR

Reversing a singly linked list isn’t some black magic—just pointer acrobatics. Do it in-place: one hand on the current node, another on the previous, the third grabbing the next guy before he ghosts you.
Brute force Java (iterative):

// Reversing a linked list, Chandler style
ListNode prev = null, curr = head;
while (curr != null) {
    ListNode next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
}
return prev;

🧠 How Devs Usually Mess This Up

First mistake: thinking [1,2,3,4,5] means you get to play with arrays. No, you get nodes—each only knows about their very next friend, not the whole party. Next up: using extra memory to make a new list (why buy an entire new wardrobe when you can just put your shirt on backwards?), or overwriting curr.next before you stash it. That’ll drop the rest of your list like a Netflix show after season two—gone and never coming back. Bonus fail: recursive solutions that forget the base case, or accidentally create the world’s weirdest infinite loop.

🔍 What’s Actually Going On

Imagine you’re walking a conga line backwards. As you pass each dancer, you turn them around to face you, until the entire line is facing the other way. In code, you’re just flipping the .next pointer of each node to look backward, one node at a time, all in-place—fewer resources than a shampoo commercial.

And yes, in interviews, the iterative trick is what they *really* want: O(n) time, O(1) space. Recursion? It’s flashier but secretly dangerous when your list is longer than your tolerance for call stack drama.

🛠️ PseudoCode

• Initialize prev = null, curr = head.
  ListNode prev = null;
ListNode curr = head;
• While curr isn’t null:
  • Temporarily store curr.next in next.
  • Point curr.next to prev (reverse the direction).
  • Slide prev forward to curr, move curr to next.

  while (curr != null) {
      ListNode next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
  }

• Once done, prev points to your new head. Return it.

For recursion, just keep diving deeper until you hit the end, then untangle yourself as you return:

💻 The Code

// Java classic: iterative
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
 public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}
 // Java: recursion (pretty, but stack-hungry)
public ListNode reverseListRecursive(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Change curr.next without saving it? You’ll lose the rest of your list like last night’s dream.
• Forget to null out the former head’s next? Enjoy creating a circular list—round and round forever.
• Try recursion on giant lists? Your call stack’s gonna throw a fit. Save that drama for HackerRank.
• Iterative: O(n) time, O(1) space. Recursive: O(n) time, O(n) space (recursion stack eats RAM for breakfast).

🧠 Interviewer Brain-Tattoo

“Don’t treat linked lists like arrays, don’t skip pointer day at the gym, and always—always!—save your spot before twisting a node around.” 💡