LeetCode Solutions Blog

Reverse Nodes in Even Length Groups

Number: 2196

Difficulty: Medium

Paid? No

Companies: Zopsmart

Problem Description

Given the head of a linked list, the nodes are sequentially partitioned into groups with sizes 1, 2, 3, etc. For each group that has an even length, reverse the nodes in that group while leaving groups with odd lengths intact. The last group may have less nodes than expected for that group size.

Key Insights

We traverse the linked list group by group, where the expected group size increases by one each time.
For each group, count the number of nodes available (which may be less than the expected size in the last group).
Reverse the nodes of a group only if its actual length is even.
Use pointer manipulation to reverse segments within the list.
Maintain O(1) extra space by reversing in place.

Space and Time Complexity

Time Complexity: O(n), where n is the total number of nodes (each node is visited once). Space Complexity: O(1) since the reversals are done in-place.

Solution

We iterate through the list while grouping nodes. For each group:

Determine the actual size of the current group (may be less than the expected group size when approaching the end).
If the group length is even, reverse the nodes in that group.
Use helper pointers to reconnect the reversed (or not reversed) group back to the list.
Increase the expected group size after processing each group. This solution involves careful management of pointers and segmentation within a linked list.

Code Solutions

# 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: ListNode) -> ListNode:
        dummy = ListNode(0, head)  # Dummy node to ease operations
        groupPrev = dummy         # Points to the node before the current group
        current = head
        groupSize = 1  # Expected group size

        while current:
            # Determine the number of nodes in current group
            count = 0
            groupEnd = current
            temp = current
            while temp and count < groupSize:
                groupEnd = temp
                temp = temp.next
                count += 1

            # If even, reverse the group
            if count % 2 == 0:
                prev = groupEnd.next  # This will be the tail of reversed group
                node = current
                # Reverse exactly 'count' nodes
                for _ in range(count):
                    nxt = node.next
                    node.next = prev
                    prev = node
                    node = nxt
                # Connect previous part to the reversed segment
                groupPrev.next = prev
                groupPrev = current
            else:
                # Move groupPrev pointer to the end of current group
                groupPrev = groupEnd
            # Move current pointer to the start of next group
            current = groupPrev.next
            groupSize += 1

        return dummy.next