Reverse Nodes In Even Length Groups

Problem#

Groups have lengths 1, 2, 3, 4, … but the last group may be shorter. For each group whose actual length is even, reverse it in place.

Examples#

[5,2,6,3,9,1,7,3,8,4] → [5,6,2,3,9,1,4,8,3,7]

Constraints#

Length in [1, 10^5].

Hints#

Hint 1

Walk one group at a time; measure its actual length first, reverse iff even.

Approach#

Track groupSize. For each group, count how many nodes are actually present (could be less than groupSize for the last group). If that count is even, reverse those nodes in place using the head-insertion trick.

Solution#

class Solution {
public:
    ListNode* reverseEvenLengthGroups(ListNode* head) {
        ListNode dummy(0, head);
        ListNode* pre = &dummy;
        int groupSize = 1;
        while (pre->next) {
            int count = 0;
            ListNode* p = pre;
            for (int i = 0; i < groupSize && p->next; ++i) { p = p->next; ++count; }
            if (count % 2 == 0) {
                ListNode* curr = pre->next;
                for (int i = 0; i < count - 1; ++i) {
                    ListNode* mover = curr->next;
                    curr->next = mover->next;
                    mover->next = pre->next;
                    pre->next = mover;
                }
                pre = curr;
            } else {
                pre = p;
            }
            ++groupSize;
        }
        return dummy.next;
    }
};

func reverseEvenLengthGroups(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    pre := dummy
    groupSize := 1
    for pre.Next != nil {
        count := 0
        p := pre
        for i := 0; i < groupSize && p.Next != nil; i++ {
            p = p.Next
            count++
        }
        if count%2 == 0 {
            curr := pre.Next
            for i := 0; i < count-1; i++ {
                mover := curr.Next
                curr.Next = mover.Next
                mover.Next = pre.Next
                pre.Next = mover
            }
            pre = curr
        } else {
            pre = p
        }
        groupSize++
    }
    return dummy.Next
}

from typing import Optional

class Solution:
    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        pre = dummy
        group_size = 1
        while pre.next:
            count = 0
            p = pre
            for _ in range(group_size):
                if p.next is None:
                    break
                p = p.next
                count += 1
            if count % 2 == 0:
                curr = pre.next
                for _ in range(count - 1):
                    mover = curr.next
                    curr.next = mover.next
                    mover.next = pre.next
                    pre.next = mover
                pre = curr
            else:
                pre = p
            group_size += 1
        return dummy.next

function reverseEvenLengthGroups(head) {
    const dummy = new ListNode(0, head);
    let pre = dummy;
    let groupSize = 1;
    while (pre.next) {
        let count = 0;
        let p = pre;
        for (let i = 0; i < groupSize && p.next; i++) {
            p = p.next;
            count++;
        }
        if (count % 2 === 0) {
            const curr = pre.next;
            for (let i = 0; i < count - 1; i++) {
                const mover = curr.next;
                curr.next = mover.next;
                mover.next = pre.next;
                pre.next = mover;
            }
            pre = curr;
        } else {
            pre = p;
        }
        groupSize++;
    }
    return dummy.next;
}

class Solution {
    public ListNode reverseEvenLengthGroups(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        int groupSize = 1;
        while (pre.next != null) {
            int count = 0;
            ListNode p = pre;
            for (int i = 0; i < groupSize && p.next != null; i++) {
                p = p.next;
                count++;
            }
            if (count % 2 == 0) {
                ListNode curr = pre.next;
                for (int i = 0; i < count - 1; i++) {
                    ListNode mover = curr.next;
                    curr.next = mover.next;
                    mover.next = pre.next;
                    pre.next = mover;
                }
                pre = curr;
            } else {
                pre = p;
            }
            groupSize++;
        }
        return dummy.next;
    }
}

function reverseEvenLengthGroups(head: ListNode | null): ListNode | null {
    const dummy = new ListNode(0, head);
    let pre: ListNode = dummy;
    let groupSize = 1;
    while (pre.next !== null) {
        let count = 0;
        let p: ListNode = pre;
        for (let i = 0; i < groupSize && p.next !== null; i++) {
            p = p.next;
            count++;
        }
        if (count % 2 === 0) {
            const curr: ListNode = pre.next;
            for (let i = 0; i < count - 1; i++) {
                const mover: ListNode = curr.next!;
                curr.next = mover.next;
                mover.next = pre.next;
                pre.next = mover;
            }
            pre = curr;
        } else {
            pre = p;
        }
        groupSize++;
    }
    return dummy.next;
}

Editorial#

Same head-insertion technique as Reverse Linked List II, but applied selectively. pre always points one node before the current group’s start, so after handling the group, advance it to the group’s tail (the new tail after possible reversal). The actual count check is crucial — the problem keys on the actual group length, not the natural number i.

Complexity#

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

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#