In-Place Linked-List Reversal

1. The signal

Reach for in-place reversal when links—not values—must be reordered and auxiliary space should stay O(1). Common forms are:

• reverse the whole list;
• reverse a sublist or every group of size k;
• reverse the second half, then merge it with the first;
• reverse one direction of a path during a more complex transformation.

2. The invariant

At the start of each iteration:

prev is the head of a completely reversed prefix, curr is the first node of the untouched suffix, and every original node is reachable from exactly one of those pointers.

Initially the reversed prefix is empty (prev = null). At the end, the untouched suffix is empty (curr = null) and prev is the new head.

3. The four-line move

ListNode* next = curr->next; // 1. preserve suffix
curr->next = prev;           // 2. reverse one edge
prev = curr;                 // 3. grow reversed prefix
curr = next;                 // 4. shrink untouched suffix

const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;

Memorise the reason, not only the order. If line 2 happens before line 1, the old successor may be lost. If the advances are swapped carelessly, both variables can end up naming the same node.

4. Whole-list template

ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

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

Time is O(n), auxiliary space is O(1), and each edge changes direction exactly once.

5. Reverse a bounded segment

For a group or sublist, initialise prev to the node after the segment rather than null. Stop when curr reaches that same boundary:

ListNode* prev = groupNext;
ListNode* curr = groupStart;
while (curr != groupNext) {
    ListNode* next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
}

Now the old group head already points to groupNext, and prev is the new group head. Only the edge from groupPrev remains to be connected.

6. Composition

Reorder List is not a new pointer trick. It composes three known pieces:

1. slow/fast to split around the middle;
2. the four-line move to reverse the second half;
3. two-list weaving with saved next pointers.

Reverse Nodes in k-Group repeats bounded reversal. Its hardness comes from boundaries and reconnection, not from a different reversal algorithm.

7. Traps

• Returning the original head after a full reversal; it is now the tail.
• Failing to terminate the first half before weaving a reordered list, creating a cycle.
• Reversing an incomplete final k-group that the problem says to preserve.
• Finding the kth node after links have already changed.
• Forgetting that groupPrev must move to the old group head after each completed reversal.

Learning gate

Write the four-line move from memory in both languages. Then hand-trace [1,2,3,4] with a table:

Do not run code until the table ends with prev = 4 and curr = null.