Linked list reversal

How does Linked list reversal work?

Keep three references: previous, current, and the one after current. previous starts as null.

Save current.next before touching anything. Otherwise the rest of the list is lost.

Point current.next at previous. That single line is the whole reversal.

Move previous to current, and current to the saved node. The window slides forward by one.

Stop when current is null. previous now points at the old last node.

Return previous rather than current. The old head has become the tail.

1. prev = null, cur = 1The list reads 1, 2, 3. Nothing is reversed yet.
2. 1 points at null, cur = 2Node 1 now points at null. It is the new tail.
3. 2 points at 1, cur = 3Node 2 points back at node 1. Two nodes are done.
4. 3 points at 2, cur = nullThe last node flips. current has run off the end.
5. head = 3prev holds the new head. Three flips in one pass.

function reverseList(head) {
    let prev = null;
    let curr = head;
    while (curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

A worked example of Linked list reversal

Reverse only part of a list

Reverse the nodes from position left to position right. Everything outside that range keeps its order.

One pass is expected, and copying values is not allowed.

Walk to the node just before left and hold on to it. Call that node the anchor.

Then pull each following node to the front of the reversed part. The anchor keeps the list joined.

function reverseBetween(head, left, right) {
    const dummy = new ListNode(0, head);

    let anchor = dummy;
    for (let i = 1; i < left; i++) anchor = anchor.next;

    const tail = anchor.next; // this node ends up last in the reversed part

    for (let i = 0; i < right - left; i++) {
        const moved = tail.next;
        tail.next = moved.next;
        moved.next = anchor.next;
        anchor.next = moved;
    }

    return dummy.next;
}

When should you use Linked list reversal?

These phrases in a problem statement point here:

• •reverse a linked list (whole list or between positions)
• •reverse in groups of k
• •no extra array or O(1) extra space allowed
• •swap pairs of nodes
• •singly linked list, only .next available

What is Linked list reversal confused with?

• Linked list merge & reorder: Merging weaves two lists into one. Reversal rewires a single list in place.
• Fast & slow pointers: That pair finds a midpoint or a cycle by walking. It never changes a link.
• Stack (LIFO): Pushing every node and popping it also reverses the order. That costs O(n) memory.
• Recursion: The recursive version reads well but uses n stack frames. The loop uses three variables.

Common mistakes with Linked list reversal

• Losing the rest of the list

  Overwriting current.next before saving it drops every later node. Save it first, every time.

• Returning the wrong node

  current is null once the loop ends. The new head is previous.

• Leaving the old head pointing somewhere

  It has to end up pointing at null. Starting previous at null does that for free.

• Using recursion on a long list

  A million nodes means a million stack frames. That overflows the call stack.

Which interview problems use Linked list reversal?

• Reverse linked list: The plain form, with three variables.
• Reverse linked list II: Only a section flips, so an anchor is needed.
• Reverse nodes in k-group: Reverse each block of k, then join the blocks.
• Palindrome linked list: Reverse the second half and compare it with the first.
• Reorder list: Split it, reverse the back half, then weave the two.
• Swap nodes in pairs: Reversal with k fixed at two.
• Add two numbers II: Reverse both lists, add them, reverse the result.

What is the time and space complexity of Linked list reversal?

O(n)

n up to 1e6 gives O(n) time and O(1) space. The recursive form instead costs O(n) stack.