Introduction

In this blog post, we will explore how to solve the LeetCode problem "2074" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. 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] 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: 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: 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 <= 105

Explanation

• Iterate through the linked list, forming groups of increasing sizes (1, 2, 3, ...).
  • For each group, check if its length is even. If so, reverse the nodes within that group.
  • Connect the reversed or non-reversed groups together to form the final modified linked list.

• Runtime Complexity: O(N), where N is the number of nodes in the linked list.
• Storage Complexity: O(1)

Code

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

def reverseEvenLengthGroups(head):
    group_length = 1
    current = head
    prev = None

    while current:
        group_head = current
        group_tail = None
        count = 0

        # Traverse the current group
        while current and count < group_length:
            group_tail = current
            current = current.next
            count += 1

        next_group_head = current

        # Check if the group length is even
        if count % 2 == 0:
            # Reverse the group
            prev_node = next_group_head
            curr_node = group_head
            while curr_node != next_group_head:
                next_node = curr_node.next
                curr_node.next = prev_node
                prev_node = curr_node
                curr_node = next_node

            # Connect the reversed group with the previous and next groups
            if prev:
                prev.next = prev_node
            else:
                head = prev_node  # Update head if it's the first group

            group_head.next = next_group_head
            prev = group_head

        else:
            # No reversal needed
            prev = group_tail

        group_length += 1

    return head