Reverse Nodes in Even Length Groups

medium linked list recursion

Problem

You are given the head of a singly linked list. Split the nodes into consecutive groups whose lengths follow the sequence 1, 2, 3, 4, and so on — the first group has 1 node, the second has 2, the third has 3, and each group is one longer than the previous. The very last group may be shorter because it just takes whatever nodes are left. For every group, reverse the nodes inside it only if that group's actual number of nodes is even. Return the head of the modified list.

Input5→2→6→3→9→1→7→3→8→4

Output5→6→2→3→9→1→4→8→3→7

Groups by size: [5] (1, odd, keep), [2,6] (2, even, reverse → 6,2), [3,9,1] (3, odd, keep), [7,3,8,4] (4, even, reverse → 4,8,3,7).

list (comma-separated)

def reverse_even_groups(head):
    prev = head
    group = 2
    while prev.next:
        node = prev
        count = 0
        while node.next and count < group:
            node = node.next
            count += 1
        if count % 2 == 0:
            cur = prev.next
            nxt = cur.next
            for _ in range(count - 1):
                cur.next = nxt.next
                nxt.next = prev.next
                prev.next = nxt
                nxt = cur.next
            prev = cur
        else:
            prev = node
        group += 1
    return head

function reverseEvenGroups(head) {
  let prev = head;
  let group = 2;
  while (prev.next) {
    let node = prev, count = 0;
    while (node.next && count < group) {
      node = node.next;
      count++;
    }
    if (count % 2 === 0) {
      let cur = prev.next, nxt = cur.next;
      for (let i = 0; i < count - 1; i++) {
        cur.next = nxt.next;
        nxt.next = prev.next;
        prev.next = nxt;
        nxt = cur.next;
      }
      prev = cur;
    } else {
      prev = node;
    }
    group++;
  }
  return head;
}

class Solution {
    public ListNode reverseEvenLengthGroups(ListNode head) {
        ListNode prev = head;
        int group = 2;
        while (prev.next != null) {
            ListNode node = prev;
            int count = 0;
            while (node.next != null && count < group) {
                node = node.next;
                count++;
            }
            if (count % 2 == 0) {
                ListNode cur = prev.next, nxt = cur.next;
                for (int i = 0; i < count - 1; i++) {
                    cur.next = nxt.next;
                    nxt.next = prev.next;
                    prev.next = nxt;
                    nxt = cur.next;
                }
                prev = cur;
            } else {
                prev = node;
            }
            group++;
        }
        return head;
    }
}

ListNode* reverseEvenLengthGroups(ListNode* head) {
    ListNode* prev = head;
    int group = 2;
    while (prev->next) {
        ListNode* node = prev;
        int count = 0;
        while (node->next && count < group) {
            node = node->next;
            count++;
        }
        if (count % 2 == 0) {
            ListNode* cur = prev->next;
            ListNode* nxt = cur->next;
            for (int i = 0; i < count - 1; i++) {
                cur->next = nxt->next;
                nxt->next = prev->next;
                prev->next = nxt;
                nxt = cur->next;
            }
            prev = cur;
        } else {
            prev = node;
        }
        group++;
    }
    return head;
}

Explanation

The list is carved into back-to-back groups whose target sizes grow as 1, 2, 3, 4, …. The catch is that the last group only gets the nodes that happen to be left over, so its real size can be smaller than its target. The decision to reverse a group depends on its actual count of nodes, not the target — reverse it only when that count is even.

The first group always has exactly one node, which is odd, so it is never reversed. That lets us start with prev pointing at the head (the node just before the second group) and begin scanning from group = 2.

Each round we first measure the upcoming group: starting from prev, we walk forward up to group steps, but stop early if the list ends. The number of steps taken is the group's true length, count.

If count is even, we splice the group's nodes into reverse order one at a time using the classic head-insertion trick, always reattaching behind prev. The node that was first in the group becomes the new tail, so we advance prev to it. If count is odd, we leave the group as-is and simply move prev to the group's last node.

Example: 5→2→6→3→9→1→7→3→8→4. Group [5] has size 1 (odd, keep). Group [2,6] has size 2 (even, reverse to 6,2). Group [3,9,1] has size 3 (odd, keep). Group [7,3,8,4] has size 4 (even, reverse to 4,8,3,7). Final list: 5→6→2→3→9→1→4→8→3→7.

Time: O(n) Space: O(1)