当前位置：首页 > 力扣 > LeetCode 2074题解：反转链表中的节点间隔（虚拟节点+分组反转）

LeetCode 2074题解：反转链表中的节点间隔（虚拟节点+分组反转）

2个月前 (07-20)

一、题目解读

LeetCode 2074题要求对链表进行分组反转：将链表按节点数分组，若当前组长度为偶数则反转该组节点，奇数长度则保持不变。例如，输入链表 [1,2,3,4,5,6]，分组后 [1,2,3,4] 反转，[5,6] 保持原序，最终输出 [4,3,2,1,5,6]。题目难点在于如何动态划分组并处理边界条件。

二、解题思路

采用“虚拟头节点+分组计数”策略：

1. 创建虚拟头节点哑元（dummy）指向原链表头，便于处理首组反转时的边界。

2. 维护变量 prev（前组尾节点）、groupNum（当前组号，即目标长度），通过循环遍历分组。

3. 每组内用 groupStart 和 groupEnd 标记起始与末尾，计数 count 实际长度。

4. 若 count 为偶数，则切断当前组末尾连接，调用反转函数 reverseList，重新拼接至原结构；奇数组则直接跳过。

5. 循环结束后返回哑元下一节点（即真实头节点）。

三、解题步骤

1. 初始化：创建哑元节点，prev 指向哑元，groupNum 从1开始（首组目标长度为1）。

2. 循环遍历：

○ 定位当前组起始 groupStart（prev->next）。

○ 通过 groupEnd 移动并计数，直至达到目标长度或链表末尾。

○ 记录下一组起始 nextGroup（groupEnd->next）。

3. 判断组长度：

○ 偶数长度：反转子链表，调整连接（prev->next 指向反转后头，groupStart->next 指向 nextGroup），更新 prev 为 groupStart。

○ 奇数长度：直接更新 prev 为 groupEnd，跳过处理。

4. 递增 groupNum 进入下一轮，重复步骤2-3直至链表结束。

5. 返回哑元下一节点（即反转后的头节点）。

四、代码及注释

class Solution {
public:
    ListNode* reverseEvenLengthGroups(ListNode* head) {
        ListNode dummy(0, head);  // 虚拟头节点，简化边界处理
        ListNode* prev = &dummy;   // 前一组尾节点
        int groupNum = 1;          // 当前组号（决定组长度）
        
        while (prev->next) {       // 循环至链表末尾
            ListNode* groupStart = prev->next;  // 当前组起始
            ListNode* groupEnd = groupStart;    // 当前组末尾（初始与起始相同）
            int count = 1;                    // 当前组实际长度计数
            
            // 确定当前组实际长度
            while (count < groupNum && groupEnd->next) {
                groupEnd = groupEnd->next;
                count++;
            }
            
            ListNode* nextGroup = groupEnd->next;  // 下一组起始节点
            if (count % 2 == 0) {                 // 偶数长度组反转
                groupEnd->next = nullptr;         // 切断末尾连接（避免反转时影响后续组）
                prev->next = reverseList(groupStart);  // 反转并连接至 prev
                groupStart->next = nextGroup;      // 连接反转后的末尾至下一组
                prev = groupStart;                 // 更新 prev 为当前组头（反转后尾节点）
            } else {                              // 奇数长度组不处理
                prev = groupEnd;                  // 更新 prev 为当前组尾
            }
            
            groupNum++;                           // 准备处理下一组（长度+1）
        }
        return dummy.next;                       // 返回真实头节点
    }
    
private:
    ListNode* reverseList(ListNode* head) {         // 辅助函数：反转子链表
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;         // 暂存后继节点
            curr->next = prev;                   // 反转指针
            prev = curr;                         // 更新 prev
            curr = next;                         // 移动至下一节点
        }
        return prev;                             // 返回反转后头节点
    }
};