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

rhsgfswg

一、题目解读

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. 返回哑元下一节点（即反转后的头节点）。

四、代码及注释

1. class Solution {
   
2. public:
   
3.     ListNode* reverseEvenLengthGroups(ListNode* head) {
   
4.         ListNode dummy(0, head);  // 虚拟头节点，简化边界处理
   
5.         ListNode* prev = &dummy;   // 前一组尾节点
   
6.         int groupNum = 1;          // 当前组号（决定组长度）
   
7.         
   
8.         while (prev->next) {       // 循环至链表末尾
   
9.             ListNode* groupStart = prev->next;  // 当前组起始
   
10.             ListNode* groupEnd = groupStart;    // 当前组末尾（初始与起始相同）
    
11.             int count = 1;                    // 当前组实际长度计数
    
12.             
    
13.             // 确定当前组实际长度
    
14.             while (count < groupNum && groupEnd->next) {
    
15.                 groupEnd = groupEnd->next;
    
16.                 count++;
    
17.             }
    
18.             
    
19.             ListNode* nextGroup = groupEnd->next;  // 下一组起始节点
    
20.             if (count % 2 == 0) {                 // 偶数长度组反转
    
21.                 groupEnd->next = nullptr;         // 切断末尾连接（避免反转时影响后续组）
    
22.                 prev->next = reverseList(groupStart);  // 反转并连接至 prev
    
23.                 groupStart->next = nextGroup;      // 连接反转后的末尾至下一组
    
24.                 prev = groupStart;                 // 更新 prev 为当前组头（反转后尾节点）
    
25.             } else {                              // 奇数长度组不处理
    
26.                 prev = groupEnd;                  // 更新 prev 为当前组尾
    
27.             }
    
28.             
    
29.             groupNum++;                           // 准备处理下一组（长度+1）
    
30.         }
    
31.         return dummy.next;                       // 返回真实头节点
    
32.     }
    
33.    
    
34. private:
    
35.     ListNode* reverseList(ListNode* head) {         // 辅助函数：反转子链表
    
36.         ListNode* prev = nullptr;
    
37.         ListNode* curr = head;
    
38.         while (curr) {
    
39.             ListNode* next = curr->next;         // 暂存后继节点
    
40.             curr->next = prev;                   // 反转指针
    
41.             prev = curr;                         // 更新 prev
    
42.             curr = next;                         // 移动至下一节点
    
43.         }
    
44.         return prev;                             // 返回反转后头节点
    
45.     }
    
46. };

复制代码

五、总结

本解法核心在于“分组计数+按需反转”的双层逻辑，通过虚拟节点避免头节点反转的边界判断。时间复杂度为 O(n)，空间复杂度为 O(1)（辅助反转函数递归栈空间可忽略）。关键点包括：

1. 利用 groupNum 动态控制分组长度，奇数组跳过，偶数组处理；

2. 反转时切断末尾连接，防止影响后续组；

3. 反转子链表的递归写法可替换为迭代优化。

来源：LeetCode 2074题解：反转链表中的节点间隔