#2074

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Reverse Nodes in Even Length Groups

Reverse nodes in even length groups while keeping the odd-length groups intact in a given linked list.

Problem Statement

You are given the head of a linked list, where nodes are grouped in sequential sizes (1, 2, 3, 4,...). In each group, the nodes are arranged consecutively.

If the group length is even, reverse the nodes in that group. If the group length is odd, leave the nodes as they are. The last group may be smaller than or equal to the second-to-last group's length.

Examples

Example 1

Input: head = [5,2,6,3,9,1,7,3,8,4]

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

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

Input: head = [1,1,0,6]

Output: [1,0,1,6]

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

Input: head = [1,1,0,6,5]

Output: [1,0,1,5,6]

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 <= 105

Solution Approach

Identify group sizes

Start by calculating the length of each group using a sequential approach. Group lengths follow the natural number sequence, so identify group boundaries at each step.

Reverse even-length groups

For every group with an even length, reverse the nodes by manipulating the next pointers. This is where linked-list pointer manipulation plays a critical role.

Handle odd-length groups

For every odd-length group, simply move the pointer forward without altering the order of nodes, ensuring only even-length groups are reversed.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the traversal and group manipulation, typically O(n), where n is the number of nodes. Space complexity is O(1) as we only manipulate pointers and do not need extra space beyond the input list.

What Interviewers Usually Probe

The candidate should understand how to manipulate pointers in a linked list.
Look for a clear separation between how even and odd-length groups are handled.
The ability to explain why the last group may not always fit the typical pattern is important.

Common Pitfalls or Variants

Common pitfalls

Failing to handle the last group when its size is smaller than expected.
Reversing odd-length groups or failing to reverse even-length groups correctly.
Not adjusting pointers properly during reversal can lead to broken lists.

Follow-up variants

What if the group lengths were randomly shuffled instead of sequential?
How would this problem change if each group could have its own predefined length?
How would you handle a situation where you need to reverse nodes in both even and odd-length groups alternatively?

FAQ

What does the problem "Reverse Nodes in Even Length Groups" focus on?

The problem focuses on reversing nodes in even-length groups of a linked list, while leaving odd-length groups untouched.

How do I handle the last group in this problem?

The last group may have fewer nodes and should be treated according to its length, reversing it if it has an even number of nodes.

Can I solve this problem with a recursive approach?

Yes, you can solve this problem recursively by processing each group and reversing it if it's even, but you still need to manage pointers carefully.

Why are odd-length groups not reversed in this problem?

Odd-length groups are not reversed to maintain the problem's specific requirement to only reverse groups with an even length.

What is the time complexity of this problem?

The time complexity is O(n), where n is the number of nodes, as you traverse the list and adjust pointers based on group lengths.

terminal

Solution

Solution 1

#### Python3

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(head, l):
            prev, cur, tail = None, head, head
            i = 0
            while cur and i < l:
                t = cur.next
                cur.next = prev
                prev = cur
                cur = t
                i += 1
            tail.next = cur
            return prev

        n = 0
        t = head
        while t:
            t = t.next
            n += 1
        dummy = ListNode(0, head)
        prev = dummy
        l = 1
        while (1 + l) * l // 2 <= n and prev:
            if l % 2 == 0:
                prev.next = reverse(prev.next, l)
            i = 0
            while i < l and prev:
                prev = prev.next
                i += 1
            l += 1
        left = n - l * (l - 1) // 2
        if left > 0 and left % 2 == 0:
            prev.next = reverse(prev.next, left)
        return dummy.next

Continue Practicing

#2058 find the minimum and maximum number of nodes between critical points #2095 delete the middle node of a linked list #2130 maximum twin sum of a linked list