Problem

You are given the head of a linked list.

The nodes in the linked list are sequentially assigned to non-empty groups whose lengths form the sequence of the natural numbers (1, 2, 3, 4, ...). The length of a group is the number of nodes assigned to it. In other words,

  • The 1st node is assigned to the first group.
  • The 2nd and the 3rd nodes are assigned to the second group.
  • The 4th, 5th, and 6th nodes are assigned to the third group, and so on.

Note that the length of the last group may be less than or equal to 1 + the length of the second to last group.

Reverse the nodes in each group with an even length, and return the head of the modified linked list.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


![](https://assets.leetcode.com/uploads/2021/10/25/eg1.png)

Input: head = [5,2,6,3,9,1,7,3,8,4]
Output: [5,6,2,3,9,1,4,8,3,7]
Explanation:
- The length of the first group is 1, which is odd, hence no reversal occurs.
- The length of the second group is 2, which is even, hence the nodes are reversed.
- The length of the third group is 3, which is odd, hence no reversal occurs.
- The length of the last group is 4, which is even, hence the nodes are reversed.

Example 2

1
2
3
4
5
6
7
8
9


![](https://assets.leetcode.com/uploads/2021/10/25/eg2.png)

Input: head = [1,1,0,6]
Output: [1,0,1,6]
Explanation:
- The length of the first group is 1. No reversal occurs.
- The length of the second group is 2. The nodes are reversed.
- The length of the last group is 1. No reversal occurs.

Example 3

1
2
3
4
5
6
7
8
9


![](https://assets.leetcode.com/uploads/2021/11/17/ex3.png)

Input: head = [1,1,0,6,5]
Output: [1,0,1,5,6]
Explanation:
- The length of the first group is 1. No reversal occurs.
- The length of the second group is 2. The nodes are reversed.
- The length of the last group is 2. The nodes are reversed.

Constraints

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

Solution

Method 1 - Group Simulation and Reverse

Intuition

We process the linked list in groups of increasing size. For each group, if its length is even, we reverse the group in-place. Otherwise, we leave it as is. This requires careful pointer manipulation.

Approach

Iterate through the list, for each group:

  • Count the actual group length (may be less than the intended size at the end).
  • If the group length is even, reverse the group and reconnect it.
  • Move to the next group, increasing the group size by 1 each time.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
    ListNode* reverseEvenLengthGroups(ListNode* head) {
        ListNode dummy(0); dummy.next = head;
        ListNode* prev = &dummy;
        int group = 1;
        while (prev->next) {
            ListNode* curr = prev->next;
            int cnt = 0;
            ListNode* node = curr;
            for (int i = 0; i < group && node; ++i, node = node->next) cnt++;
            if (cnt % 2 == 0) {
                ListNode* tail = curr;
                ListNode* next = curr;
                for (int i = 0; i < cnt; ++i) next = next->next;
                ListNode* prev2 = next;
                for (int i = 0; i < cnt; ++i) {
                    ListNode* tmp = curr->next;
                    curr->next = prev2;
                    prev2 = curr;
                    curr = tmp;
                }
                prev->next = prev2;
                prev = tail;
            } else {
                for (int i = 0; i < cnt; ++i) prev = prev->next;
            }
            group++;
        }
        return dummy.next;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

type ListNode struct {
    Val int
    Next *ListNode
}
func reverseEvenLengthGroups(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    prev := dummy
    group := 1
    for prev.Next != nil {
        curr := prev.Next
        cnt := 0
        node := curr
        for i := 0; i < group && node != nil; i++ {
            cnt++
            node = node.Next
        }
        if cnt%2 == 0 {
            tail := curr
            next := curr
            for i := 0; i < cnt; i++ { next = next.Next }
            prev2 := next
            for i := 0; i < cnt; i++ {
                tmp := curr.Next
                curr.Next = prev2
                prev2 = curr
                curr = tmp
            }
            prev.Next = prev2
            prev = tail
        } else {
            for i := 0; i < cnt; i++ { prev = prev.Next }
        }
        group++
    }
    return dummy.Next
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
class Solution {
    public ListNode reverseEvenLengthGroups(ListNode head) {
        ListNode dummy = new ListNode(0); dummy.next = head;
        ListNode prev = dummy;
        int group = 1;
        while (prev.next != null) {
            ListNode curr = prev.next;
            int cnt = 0;
            ListNode node = curr;
            for (int i = 0; i < group && node != null; i++, node = node.next) cnt++;
            if (cnt % 2 == 0) {
                ListNode tail = curr;
                ListNode next = curr;
                for (int i = 0; i < cnt; i++) next = next.next;
                ListNode prev2 = next;
                for (int i = 0; i < cnt; i++) {
                    ListNode tmp = curr.next;
                    curr.next = prev2;
                    prev2 = curr;
                    curr = tmp;
                }
                prev.next = prev2;
                prev = tail;
            } else {
                for (int i = 0; i < cnt; i++) prev = prev.next;
            }
            group++;
        }
        return dummy.next;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class ListNode(var `val`: Int) {
    var next: ListNode? = null
}
class Solution {
    fun reverseEvenLengthGroups(head: ListNode?): ListNode? {
        val dummy = ListNode(0)
        dummy.next = head
        var prev: ListNode? = dummy
        var group = 1
        while (prev?.next != null) {
            var curr = prev.next
            var cnt = 0
            var node = curr
            repeat(group) {
                if (node != null) {
                    cnt++
                    node = node.next
                }
            }
            if (cnt % 2 == 0) {
                val tail = curr
                var next = curr
                repeat(cnt) { next = next?.next }
                var prev2 = next
                repeat(cnt) {
                    val tmp = curr?.next
                    curr?.next = prev2
                    prev2 = curr
                    curr = tmp
                }
                prev.next = prev2
                prev = tail
            } else {
                repeat(cnt) { prev = prev?.next }
            }
            group++
        }
        return dummy.next
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseEvenLengthGroups(self, head: ListNode) -> ListNode:
        dummy = ListNode(0, head)
        prev = dummy
        group = 1
        while prev.next:
            curr = prev.next
            cnt = 0
            node = curr
            for _ in range(group):
                if node:
                    cnt += 1
                    node = node.next
            if cnt % 2 == 0:
                tail = curr
                next_ = curr
                for _ in range(cnt):
                    next_ = next_.next
                prev2 = next_
                for _ in range(cnt):
                    tmp = curr.next
                    curr.next = prev2
                    prev2 = curr
                    curr = tmp
                prev.next = prev2
                prev = tail
            else:
                for _ in range(cnt):
                    prev = prev.next
            group += 1
        return dummy.next
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

// Leetcode's ListNode definition
// pub struct ListNode { pub val: i32, pub next: Option<Box<ListNode>> }
impl Solution {
    pub fn reverse_even_length_groups(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
        let mut prev = dummy.as_mut();
        let mut group = 1;
        while let Some(p) = prev {
            let mut curr = p.next.as_mut();
            let mut cnt = 0;
            let mut node = curr.as_ref();
            for _ in 0..group {
                if let Some(n) = node {
                    cnt += 1;
                    node = n.next.as_ref();
                }
            }
            if cnt % 2 == 0 && cnt > 0 {
                // Reverse cnt nodes
                let mut next = curr.as_mut();
                for _ in 0..cnt { if let Some(n) = next { next = n.next.as_mut(); } }
                let mut prev2 = next;
                for _ in 0..cnt {
                    if let Some(mut c) = curr.take() {
                        let tmp = c.next.take();
                        c.next = prev2.take();
                        prev2 = Some(c);
                        curr = tmp;
                    }
                }
                p.next = prev2;
                for _ in 0..cnt { if let Some(n) = p.next.as_mut() { p = n; } }
                prev = Some(p);
            } else {
                for _ in 0..cnt { if let Some(n) = prev { prev = n.next.as_mut(); } }
            }
            group += 1;
        }
        dummy.unwrap().next
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.next = (next===undefined ? null : next)
    }
}
function reverseEvenLengthGroups(head: ListNode | null): ListNode | null {
    const dummy = new ListNode(0, head)
    let prev: ListNode | null = dummy
    let group = 1
    while (prev && prev.next) {
        let curr = prev.next
        let cnt = 0
        let node = curr
        for (let i = 0; i < group && node; i++, node = node.next) cnt++
        if (cnt % 2 === 0) {
            let tail = curr
            let next: ListNode | null = curr
            for (let i = 0; i < cnt; i++) next = next!.next
            let prev2: ListNode | null = next
            for (let i = 0; i < cnt; i++) {
                let tmp = curr!.next
                curr!.next = prev2
                prev2 = curr
                curr = tmp
            }
            prev.next = prev2
            prev = tail
        } else {
            for (let i = 0; i < cnt; i++) prev = prev!.next
        }
        group++
    }
    return dummy.next
}

Complexity

  • ⏰ Time complexity: O(n) — each node is visited a constant number of times.
  • 🧺 Space complexity: O(1) — in-place reversal, no extra space except pointers.