← Bank
DSA

Reverse a Linked List

DSAJunior~12m
linked-listspointersrecursion

Prompt

We store each user's recent activity as a singly linked list, newest event at the head. Product wants to render it oldest-first. Walk me through how you'd reverse that list in place.

How this round runs

I'm not telling you up front whether recursion is allowed or how long these lists get — clarify that before you commit to an approach, and expect a twist once you have something working.

Model answer

Clarify first: can I mutate the existing nodes in place, or do I need a fresh list? How long can these lists get — are we at risk of a deep call stack? Is the input ever null or a single node?

The core idea is rewiring each next pointer to point backward. Brute force would be to copy values into an array and rebuild — O(n) time but O(n) extra space and it sidesteps the actual pointer work. Better: an in-place iterative walk with three pointers — prev, current, and a saved next so we don't lose the rest of the list when we flip a link. That's O(n) time and O(1) space.

function reverse(head) {
  let prev = null;
  let current = head;
  while (current !== null) {
    const next = current.next; // save before we clobber it
    current.next = prev;        // flip the link backward
    prev = current;             // advance prev
    current = next;             // advance current
  }
  return prev; // old tail is the new head
}

Dry-run on 1 -> 2 -> 3: save next=2, point 1 back to null, prev=1, current=2; save next=3, point 2 back to 1, prev=2, current=3; save next=null, point 3 back to 2, prev=3, current=null; loop ends, return 3. List is now 3 -> 2 -> 1.

The recursive form recurses to the tail, then on the way back sets head.next.next = head and head.next = null. Clean to read, but it's O(n) stack space and risks a stack overflow on a very long activity log — which is why I'd default to iterative here.

Signals — what a strong answer shows
  • Asked whether in-place mutation is allowed and how long the lists get
  • Saved the next pointer before reversing, and said why that order matters
  • Stated O(n) time and O(1) space for the iterative approach
  • Dry-ran the pointer moves on a 3-node list
Follow-ups — where it goes next
  • Now do it recursively → tail base case, rewire on the unwind, note the O(n) stack cost
  • Reverse only the sub-range between positions m and n → splice out the segment, reverse it, stitch the boundaries back