Medium

题目描述

给你一个链表的头节点 head。

链表中的节点按顺序划分到若干个非空组中，这些组的长度构成一个自然数序列（1, 2, 3, 4, …）。一个组的长度就是分配给它的节点数目。换句话说：

  • 第 1 个节点分配给第一组
  • 第 2 和第 3 个节点分配给第二组
  • 第 4、5、6 个节点分配给第三组，依此类推

注意，最后一组的长度可能小于或等于 1 + 倒数第二组的长度。

反转每个 偶数 长度组中的节点，返回修改后链表的头节点。

示例 1：

输入：head = [5,2,6,3,9,1,7,3,8,4]
输出：[5,6,2,3,9,1,4,8,3,7]
解释：
- 第一组长度为 1，是奇数，不反转
- 第二组长度为 2，是偶数，反转节点  
- 第三组长度为 3，是奇数，不反转
- 最后一组长度为 4，是偶数，反转节点

示例 2：

输入：head = [1,1,0,6]
输出：[1,0,1,6]
解释：
- 第一组长度为 1，不反转
- 第二组长度为 2，反转节点
- 最后一组长度为 1，不反转

示例 3：

输入：head = [1,1,0,6,5]  
输出：[1,0,1,5,6]
解释：
- 第一组长度为 1，不反转
- 第二组长度为 2，反转节点
- 最后一组长度为 2，反转节点

提示：

  • 链表中节点数目范围是 [1, 10^5]
  • 0 <= Node.val <= 10^5

解题思路

这道题的关键在于理解分组规律和链表反转操作。

分组规律分析：

  • 第1组：1个节点（索引0）
  • 第2组：2个节点（索引1-2）
  • 第3组：3个节点（索引3-5）
  • 第4组：4个节点（索引6-9）
  • …

每组的起始位置为 (k-1)*k/2，其中k为组号。

解决思路：

  1. 遍历每个分组：按照1,2,3,4…的长度依次处理每个分组
  2. 判断分组长度：如果当前分组的实际长度为偶数，则需要反转
  3. 链表反转：使用标准的链表反转算法反转当前分组
  4. 连接处理：正确连接反转后的分组与前后节点

实现细节：

  • 使用四个指针：prev（前一组末尾）、start（当前组开头）、end（当前组末尾）、next（下一组开头）
  • 先确定当前分组的实际长度，可能小于预期长度（最后一组）
  • 如果长度为偶数，反转start到end这段链表
  • 更新连接关系：prev->next = end，start->next = next

这种方法时间复杂度为O(n)，空间复杂度为O(1)，是最优解法。

代码实现

class Solution {
public:
    ListNode* reverseEvenLengthGroups(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        int groupSize = 1;
        
        while (curr) {
            ListNode* groupStart = curr;
            ListNode* groupEnd = curr;
            
            // 找到当前组的结束位置
            int actualSize = 0;
            for (int i = 0; i < groupSize && curr; i++) {
                groupEnd = curr;
                curr = curr->next;
                actualSize++;
            }
            
            // 如果组长度为偶数，反转该组
            if (actualSize % 2 == 0) {
                ListNode* nextGroup = curr;
                
                // 反转链表
                ListNode* prevNode = nextGroup;
                ListNode* currNode = groupStart;
                
                while (currNode != nextGroup) {
                    ListNode* nextNode = currNode->next;
                    currNode->next = prevNode;
                    prevNode = currNode;
                    currNode = nextNode;
                }
                
                // 连接反转后的组
                if (prev) {
                    prev->next = groupEnd;
                } else {
                    head = groupEnd;
                }
                prev = groupStart;
            } else {
                prev = groupEnd;
            }
            
            groupSize++;
        }
        
        return head;
    }
};

class Solution:
    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        group_size = 1
        
        while curr:
            group_start = curr
            group_end = curr
            
            # 找到当前组的结束位置
            actual_size = 0
            for i in range(group_size):
                if not curr:
                    break
                group_end = curr
                curr = curr.next
                actual_size += 1
            
            # 如果组长度为偶数，反转该组
            if actual_size % 2 == 0:
                next_group = curr
                
                # 反转链表
                prev_node = next_group
                curr_node = group_start
                
                while curr_node != next_group:
                    next_node = curr_node.next
                    curr_node.next = prev_node
                    prev_node = curr_node
                    curr_node = next_node
                
                # 连接反转后的组
                if prev:
                    prev.next = group_end
                else:
                    head = group_end
                prev = group_start
            else:
                prev = group_end
            
            group_size += 1
        
        return head

public class Solution {
    public ListNode ReverseEvenLengthGroups(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        int groupSize = 1;
        
        while (curr != null) {
            ListNode groupStart = curr;
            ListNode groupEnd = curr;
            
            // 找到当前组的结束位置
            int actualSize = 0;
            for (int i = 0; i < groupSize && curr != null; i++) {
                groupEnd = curr;
                curr = curr.next;
                actualSize++;
            }
            
            // 如果组长度为偶数，反转该组
            if (actualSize % 2 == 0) {
                ListNode nextGroup = curr;
                
                // 反转链表
                ListNode prevNode = nextGroup;
                ListNode currNode = groupStart;
                
                while (currNode != nextGroup) {
                    ListNode nextNode = currNode.next;
                    currNode.next = prevNode;
                    prevNode = currNode;
                    currNode = nextNode;
                }
                
                // 连接反转后的组
                if (prev != null) {
                    prev.next = groupEnd;
                } else {
                    head = groupEnd;
                }
                prev = groupStart;
            } else {
                prev = groupEnd;
            }
            
            groupSize++;
        }
        
        return head;
    }
}

var reverseEvenLengthGroups = function(head) {
    let prev = null;
    let curr = head;
    let groupSize = 1;
    
    while (curr) {
        // Count nodes in current group
        let count = 0;
        let temp = curr;
        while (temp && count < groupSize) {
            temp = temp.next;
            count++;
        }
        
        // If group has even length, reverse it
        if (count % 2 === 0) {
            let groupPrev = prev;
            let groupCurr = curr;
            let reversePrev = null;
            
            // Reverse the group
            for (let i = 0; i < count; i++) {
                let next = groupCurr.next;
                groupCurr.next = reversePrev;
                reversePrev = groupCurr;
                groupCurr = next;
            }
            
            // Connect reversed group
            if (groupPrev) {
                groupPrev.next = reversePrev;
            } else {
                head = reversePrev;
            }
            curr.next = groupCurr;
            prev = curr;
            curr = groupCurr;
        } else {
            // Skip odd length group
            for (let i = 0; i < count; i++) {
                prev = curr;
                curr = curr.next;
            }
        }
        
        groupSize++;
    }
    
    return head;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个节点最多被访问常数次，总体为线性时间
空间复杂度O(1)只使用了有限个额外指针变量，常数空间

相关题目