Reverse a Linked List In Place — Iterative Template and k-Group

Reversing a list is the "can you manipulate pointers without losing the list" check. It appears as a step inside larger problems far more often than on its own — palindrome checks, reordering, k-group reversal — so the loop needs to be automatic.

The idea

Walk the list, flipping each next pointer to face backwards. Three pointers, because overwriting curr.next destroys your only route forward unless you saved it first.

def reverse_list(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next        # 1. save the rest of the list
        curr.next = prev       # 2. flip this link
        prev = curr            # 3. shuffle both pointers forward
        curr = nxt
    return prev                # curr is None here; prev is the new head

ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;   // 1. save the rest of the list
        curr.next = prev;            // 2. flip this link
        prev = curr;                 // 3. shuffle both pointers forward
        curr = next;
    }
    return prev;    // curr is null here; prev is the new head
}

ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head;
    while (curr) {
        ListNode* next = curr->next;  // 1. save the rest of the list
        curr->next = prev;            // 2. flip this link
        prev = curr;                  // 3. shuffle both pointers forward
        curr = next;
    }
    return prev;    // curr is null here; prev is the new head
}

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL, *curr = head;
    while (curr) {
        struct ListNode* next = curr->next;  /* 1. save the rest */
        curr->next = prev;                   /* 2. flip this link */
        prev = curr;                         /* 3. advance both */
        curr = next;
    }
    return prev;    /* curr is NULL here; prev is the new head */
}

function reverseList(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;   // 1. save the rest of the list
    curr.next = prev;         // 2. flip this link
    prev = curr;              // 3. shuffle both pointers forward
    curr = next;
  }
  return prev;   // curr is null here; prev is the new head
}

Four lines in a fixed order. Write them in any other order and the list is gone. Returning prev rather than curr is the other reliable slip: when the loop exits curr is None and prev is the last node visited, which is the new head.

The recursive form is shorter but O(n) stack, and interviewers usually want the iterative one for that reason:

def reverse_recursive(head):
    if not head or not head.next:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head       # the node ahead now points back at us
    head.next = None
    return new_head

ListNode reverseRecursive(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseRecursive(head.next);
    head.next.next = head;     // the node ahead now points back at us
    head.next = null;
    return newHead;            // O(n) stack — say so if you offer this
}

ListNode* reverseRecursive(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* newHead = reverseRecursive(head->next);
    head->next->next = head;   // the node ahead now points back at us
    head->next = nullptr;
    return newHead;            // O(n) stack
}

struct ListNode* reverseRecursive(struct ListNode* head) {
    if (!head || !head->next) return head;
    struct ListNode* newHead = reverseRecursive(head->next);
    head->next->next = head;   /* the node ahead now points back at us */
    head->next = NULL;
    return newHead;            /* O(n) stack */
}

function reverseRecursive(head) {
  if (!head || !head.next) return head;
  const newHead = reverseRecursive(head.next);
  head.next.next = head;    // the node ahead now points back at us
  head.next = null;
  return newHead;           // O(n) stack — say so if you offer this
}

Reversing a sublist

Reverse Linked List II reverses positions left..right and leaves the rest alone. The

difficulty is entirely in the stitching, and a dummy node removes most of it.

def reverse_between(head, left, right):
    dummy = ListNode(0, head)          # so "reverse from position 1" needs no special case
    before = dummy
    for _ in range(left - 1):
        before = before.next           # node just before the reversed section

    prev, curr = None, before.next
    tail = curr                        # this becomes the section's last node
    for _ in range(right - left + 1):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt

    before.next = prev                 # stitch the front
    tail.next = curr                   # stitch the back
    return dummy.next

ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(0, head);   // removes the left == 1 special case
    ListNode before = dummy;
    for (int i = 0; i < left - 1; i++) before = before.next;

    ListNode prev = null, curr = before.next;
    ListNode tail = curr;                     // becomes the section's last node
    for (int i = 0; i < right - left + 1; i++) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    before.next = prev;      // stitch the front
    tail.next = curr;        // stitch the back
    return dummy.next;
}

ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode dummy(0);
    dummy.next = head;                   // removes the left == 1 special case
    ListNode* before = &dummy;
    for (int i = 0; i < left - 1; i++) before = before->next;

    ListNode *prev = nullptr, *curr = before->next;
    ListNode* tail = curr;               // becomes the section's last node
    for (int i = 0; i < right - left + 1; i++) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }

    before->next = prev;     // stitch the front
    tail->next = curr;       // stitch the back
    return dummy.next;
}

function reverseBetween(head, left, right) {
  const dummy = { val: 0, next: head };   // removes the left === 1 special case
  let before = dummy;
  for (let i = 0; i < left - 1; i++) before = before.next;

  let prev = null, curr = before.next;
  const tail = curr;                      // becomes the section's last node
  for (let i = 0; i < right - left + 1; i++) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  before.next = prev;    // stitch the front
  tail.next = curr;      // stitch the back
  return dummy.next;
}

Without the dummy, left == 1 needs its own branch because there is no node before the section. Adding a fake head is the standard way to make every linked-list edit uniform, and it is worth reaching for by reflex.

Reverse Nodes in k-Group

The Hard variant, and pure composition: walk forward k nodes to check a full group exists, reverse exactly those k, stitch, and repeat from the new tail.

def reverse_k_group(head, k):
    dummy = ListNode(0, head)
    group_prev = dummy

    while True:
        kth = group_prev
        for _ in range(k):             # is there a full group left?
            kth = kth.next
            if not kth:
                return dummy.next      # leftover tail stays as-is

        group_next = kth.next
        prev, curr = group_next, group_prev.next
        while curr is not group_next:  # reverse the group, tail already stitched
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        tail = group_prev.next         # old head is the new tail
        group_prev.next = kth
        group_prev = tail

ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0, head);
    ListNode groupPrev = dummy;

    while (true) {
        ListNode kth = groupPrev;
        for (int i = 0; i < k; i++) {       // is there a full group left?
            kth = kth.next;
            if (kth == null) return dummy.next;   // leftover tail stays as-is
        }

        ListNode groupNext = kth.next;
        // Seeding prev with groupNext means the group's tail is already
        // stitched to the rest when the loop finishes.
        ListNode prev = groupNext, curr = groupPrev.next;
        while (curr != groupNext) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        ListNode tail = groupPrev.next;     // old head is the new tail
        groupPrev.next = kth;
        groupPrev = tail;
    }
}

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* groupPrev = &dummy;

    while (true) {
        ListNode* kth = groupPrev;
        for (int i = 0; i < k; i++) {          // is there a full group left?
            kth = kth->next;
            if (!kth) return dummy.next;       // leftover tail stays as-is
        }

        ListNode* groupNext = kth->next;
        // Seeding prev with groupNext stitches the group's tail up front.
        ListNode *prev = groupNext, *curr = groupPrev->next;
        while (curr != groupNext) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }

        ListNode* tail = groupPrev->next;      // old head is the new tail
        groupPrev->next = kth;
        groupPrev = tail;
    }
}

function reverseKGroup(head, k) {
  const dummy = { val: 0, next: head };
  let groupPrev = dummy;

  while (true) {
    let kth = groupPrev;
    for (let i = 0; i < k; i++) {          // is there a full group left?
      kth = kth.next;
      if (!kth) return dummy.next;         // leftover tail stays as-is
    }

    const groupNext = kth.next;
    // Seeding prev with groupNext stitches the group's tail up front.
    let prev = groupNext, curr = groupPrev.next;
    while (curr !== groupNext) {
      const next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }

    const tail = groupPrev.next;           // old head is the new tail
    groupPrev.next = kth;
    groupPrev = tail;
  }
}

The trick that keeps it short: seeding prev = group_next means the group's last link is already pointing at the rest of the list when the loop finishes, so only the front needs stitching afterwards.

Complexity

O(n) time and O(1) space for every iterative version — each node's pointer is rewritten once. The recursive version is O(n) time but O(n) stack, which is a real difference on a long list and a fair thing to be asked about.

Mistakes that cost the round

Reordering the four lines. Save, flip, advance, advance. Flipping before saving

drops the tail of the list.

Returning `curr` — it is None at the end. Return prev.
Not using a dummy node on sublist problems, then discovering left == 1 needs a

whole separate branch.

Losing the group's tail in k-group: the old head is the new tail, and it is what

the next group must attach to.

Reversing a partial trailing group. The problem says leave fewer than k nodes

as-is; check the full group exists before touching anything.

What to drill

Reverse Linked List — the three-pointer loop, until it is automatic.
Reverse Linked List II — the dummy node and the two stitches.
Reverse Nodes in k-Group — the composition of both.

All on the 22 DSA Patterns sheet. Reversal also shows up as a step in Palindrome Linked List, which is where the fast and slow pointer pattern hands off to this one.

Frequently asked

How do you reverse a linked list in place?

Keep three pointers — prev, curr and a saved next. In each iteration: save curr.next, point curr.next at prev, then move prev to curr and curr to the saved node. When curr is null, prev is the new head. O(n) time, O(1) space.

Why use a dummy node when reversing part of a list?

It gives you a real node before the head, so reversing a section that starts at position 1 needs no special case — you always have a before node to stitch the reversed section onto. Returning dummy.next at the end handles a changed head automatically.

Is the recursive reversal acceptable in an interview?

It is correct and shorter, but it uses O(n) stack space and will overflow on a long list. Mention that trade-off and offer the iterative version — the O(1) space is usually the point of asking.

Reversal of Linked List (In-place)