We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Reverse Nodes in Even Length Groups

Difficulty: Medium

Problem Description

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, ...). Reverse the nodes in each group with an even length, and return the head of the modified linked list.

Key Insights

  • The linked list is divided into groups based on the natural number sequence, where the first group has 1 node, the second group has 2 nodes, the third has 3 nodes, and so forth.
  • Only groups with an even number of nodes are reversed.
  • The last group may have fewer nodes than expected due to the total number of nodes in the linked list.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list. Space Complexity: O(1), as we are modifying the list in place without using extra space proportional to the input size.

Solution

To solve the problem, we will employ a two-pointer approach. We will iterate through the linked list to identify the groups based on their lengths. For each group, we will check if its length is even. If it is, we will reverse the nodes in that group. We will maintain pointers to connect the reversed groups back to the main list. This approach efficiently handles the reversal and connection of groups without needing additional data structures.

Code Solutions

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

def reverseEvenLengthGroups(head):
    dummy = ListNode(0)
    dummy.next = head
    prev_group_end = dummy
    current = head
    group_length = 1

    while current:
        group_start = current
        count = 0
        
        # Traverse the current group
        while current and count < group_length:
            count += 1
            current = current.next
            
        if count % 2 == 0:
            # Reverse the current group
            prev = None
            curr = group_start
            for _ in range(count):
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node
            
            # Connect reversed group back to previous part of the list
            prev_group_end.next = prev
            group_start.next = current
            prev_group_end = group_start
        else:
            # Just connect back to the next group
            prev_group_end.next = group_start

        group_length += 1

    return dummy.next
← Back to All Questions