Reverse Nodes in Even Length Groups

Medium
2019.

Reverse Nodes in Even Length Groups

MediumLinked ListSimulationAmazonGoogle

Reverse Nodes in Even Length Groups is a medium coding problem on simulation, asked in Amazon and Google interviews.

You are given the head of a singly linked list. Cut the list, from the front, into consecutive groups whose intended sizes are 1, 2, 3, 4, … — the first node alone, the next two nodes, the next three, and so on. The last group takes whatever nodes remain, so its actual length may be smaller than its intended size.

Reverse the nodes of every group whose actual length is even, leave the odd-length groups as they are, and return the head of the resulting list.

Example 1

Input
head = [8,1,4,2,7,5,9,3,6,0]
Output
[8,4,1,2,7,5,0,6,3,9]
Explanation
The groups are [8], [1,4], [2,7,5] and [9,3,6,0]. Only the groups of length 2 and 4 are even, so they are reversed.

Example 2

Input
head = [3,7,1,4]
Output
[3,1,7,4]
Explanation
The groups are [3], [7,1] and [4]. The last group was meant to hold three nodes but only one is left — its length is 1, odd, so it stays.

Example 3

Input
head = [2,6,9,1,5]
Output
[2,9,6,5,1]
Explanation
The groups are [2], [6,9] and [1,5]. The last group has only two nodes, an even length, so it is reversed too.

Constraints

  • The number of nodes in the list is in the range [1, 10^5]
  • 0 <= Node.val <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseEvenLengthGroups = function(head) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Reverse Nodes in Even Length Groups — Problem & Solution

Reverse Nodes in Even Length Groups solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Reverse Nodes in Even Length Groups is a medium coding problem on simulation, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Simulation
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given the head of a singly linked list. Cut the list, from the front, into consecutive groups whose intended sizes are 1, 2, 3, 4, … — the first node alone, the next two nodes, the next three, and so on. The last group takes whatever nodes remain, so its actual length may be smaller than its intended size.

Reverse the nodes of every group whose actual length is even, leave the odd-length groups as they are, and return the head of the resulting list.

Example 1

Input: head = [8,1,4,2,7,5,9,3,6,0]
Output: [8,4,1,2,7,5,0,6,3,9]
Explanation: The groups are [8], [1,4], [2,7,5] and [9,3,6,0]. Only the groups of length 2 and 4 are even, so they are reversed.

Example 2

Input: head = [3,7,1,4]
Output: [3,1,7,4]
Explanation: The groups are [3], [7,1] and [4]. The last group was meant to hold three nodes but only one is left — its length is 1, odd, so it stays.

Example 3

Input: head = [2,6,9,1,5]
Output: [2,9,6,5,1]
Explanation: The groups are [2], [6,9] and [1,5]. The last group has only two nodes, an even length, so it is reversed too.

Constraints

  • The number of nodes in the list is in the range [1, 10^5]
  • 0 <= Node.val <= 10^5

Hints for Reverse Nodes in Even Length Groups

  1. Hint 1

    The decision for each group depends on its actual length, which only differs from the intended size for the last group — count before you reverse.

  2. Hint 2

    Keep a pointer to the node just before the current group. Walk at most size nodes ahead to learn the group's real length and the node that follows it.

  3. Hint 3

    Reversing a run of k nodes in place: start the reversed run pointing at the node after the group, then relink each node in turn; afterwards the old first node of the group is the new tail and the next group's predecessor.

How to solve Reverse Nodes in Even Length Groups

Walk the list group by group, remembering the node before the group. For each group first count how many nodes it really has (at most its intended size), and reverse exactly those nodes in place when the count is even.

Approach

  1. The first group is the head alone — length 1, never reversed — so start with prev = head and the intended size 2.
  2. While prev.next exists, walk from prev.next up to size nodes, counting them in cnt; node ends at the first node after the group.
  3. If cnt is even, reverse the cnt nodes: set rev = node, then for each node of the group point it at rev and make it the new rev. Link prev.next = rev, and move prev to the group's old first node, which is now its last.
  4. If cnt is odd, just advance prev by cnt nodes.
  5. Increase size by one and continue; return head, which never changes.

Why it works

Every group is handled exactly once and only its own links change. Starting the reversed run at the node after the group keeps the rest of the list attached, and the old first node of the group becomes the predecessor of the next group, so the walk continues from the right place.

Complexity

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

Pitfalls

  • Deciding by the intended size: a last group meant to hold 5 nodes that only has 4 must be reversed.
  • Forgetting to reconnect the reversed group's tail to the following node — the counting walk already found it.
  • The head never moves, because the first group has length 1.

Reference solution

Python

from typing import Optional

def reverseEvenLengthGroups(head: Optional[ListNode]) -> Optional[ListNode]:
    prev = head  # the first group is the head alone: length 1, never reversed
    size = 2
    while prev.next:
        node, cnt = prev.next, 0
        while node and cnt < size:
            node = node.next
            cnt += 1
        if cnt % 2 == 0:
            first = cur = prev.next
            rev = node
            for _ in range(cnt):
                nxt = cur.next
                cur.next = rev
                rev = cur
                cur = nxt
            prev.next = rev
            prev = first
        else:
            for _ in range(cnt):
                prev = prev.next
        size += 1
    return head

Java

public static ListNode reverseEvenLengthGroups(ListNode head) {
    ListNode prev = head; // the first group is the head alone
    int size = 2;
    while (prev.next != null) {
        ListNode node = prev.next;
        int cnt = 0;
        while (node != null && cnt < size) { node = node.next; cnt++; }
        if (cnt % 2 == 0) {
            ListNode first = prev.next, cur = prev.next, rev = node;
            for (int i = 0; i < cnt; i++) { ListNode nxt = cur.next; cur.next = rev; rev = cur; cur = nxt; }
            prev.next = rev;
            prev = first;
        } else {
            for (int i = 0; i < cnt; i++) prev = prev.next;
        }
        size++;
    }
    return head;
}

C++

ListNode* reverseEvenLengthGroups(ListNode* head) {
    ListNode* prev = head; // the first group is the head alone
    int size = 2;
    while (prev->next) {
        ListNode* node = prev->next;
        int cnt = 0;
        while (node && cnt < size) { node = node->next; cnt++; }
        if (cnt % 2 == 0) {
            ListNode *first = prev->next, *cur = prev->next, *rev = node;
            for (int i = 0; i < cnt; i++) { ListNode* nxt = cur->next; cur->next = rev; rev = cur; cur = nxt; }
            prev->next = rev;
            prev = first;
        } else {
            for (int i = 0; i < cnt; i++) prev = prev->next;
        }
        size++;
    }
    return head;
}

JavaScript

var reverseEvenLengthGroups = function(head) {
    var prev = head, size = 2; // the first group is the head alone
    while (prev.next !== null) {
        var node = prev.next, cnt = 0;
        while (node !== null && cnt < size) { node = node.next; cnt++; }
        if (cnt % 2 === 0) {
            var first = prev.next, cur = prev.next, rev = node;
            for (var i = 0; i < cnt; i++) { var nxt = cur.next; cur.next = rev; rev = cur; cur = nxt; }
            prev.next = rev;
            prev = first;
        } else {
            for (var j = 0; j < cnt; j++) prev = prev.next;
        }
        size++;
    }
    return head;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 137 simulation problems · the whole catalogue