Reverse Nodes in Even-Length Groups — Group Counting

Sanjeev SharmaSanjeev Sharma
2 min read

Advertisement

Problem 239 · Reverse Nodes in Even Length Groups

Difficulty: Medium · Pattern: Group Reversal

Groups are sized 1, 2, 3, 4, ... Reverse each group that has an even number of nodes.

Solutions

# Python
def reverseEvenLengthGroups(head):
    prev = head  # prev group's last node
    group_len = 2  # current expected group size
    while prev.next:
        # Count actual nodes in this group
        node = prev
        count = 0
        while node.next and count < group_len:
            node = node.next; count += 1
        group_len += 1
        if count % 2 == 0:
            # Reverse 'count' nodes starting from prev.next
            tail = prev.next
            cur = tail.next
            for _ in range(count - 1):
                tail.next = cur.next
                cur.next = prev.next
                prev.next = cur
                cur = tail.next
        prev = node
    return head
// Java
public ListNode reverseEvenLengthGroups(ListNode head) {
    ListNode prev = head;
    for (int groupLen = 2; prev.next != null; groupLen++) {
        ListNode node = prev; int count = 0;
        while (node.next != null && count < groupLen) { node = node.next; count++; }
        if (count % 2 == 0) {
            ListNode tail = prev.next, cur = tail.next;
            for (int i = 0; i < count-1; i++) {
                tail.next = cur.next; cur.next = prev.next; prev.next = cur; cur = tail.next;
            }
        }
        prev = node;
    }
    return head;
}

Complexity

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

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro