题目描述

给你链表的头节点 head，每 k 个节点一组进行翻转，请你返回修改后的链表。

• k 是正整数，且小于等于链表长度。

• 如果节点总数不是 k 的整数倍，最后剩余节点保持原顺序。

• 禁止直接修改节点值，必须实际改变节点指向。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

---

解题思路

这题核心思想是：

1. 每 k 个节点为一组，进行局部反转；

2. 最后一组节点不足 k 个时，保持原样；

3. 链表操作时要小心指针连接。

具体步骤：

1. 用 dummy 节点方便处理头节点；

2. 用两个指针：

   • pre：指向当前组的前一个节点

   • end：用于找到当前组的第 k 个节点

3. 循环处理每一组：

   1. 找到 [start, end] 区间；

   2. 断开链表；

   3. 反转这一段；

   4. 接回原链表；

   5. 更新 pre 指向下一组的前节点。

---

代码实现（C语言）

// 反转整个链表
struct ListNode* reverse(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    
    while (cur) {
        struct ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    if (!head || k == 1) return head;

    struct ListNode dummy;
    dummy.next = head;

    struct ListNode* pre = &dummy;
    struct ListNode* end = &dummy;

    while (1) {
        // 1. 找到第 k 个节点
        for (int i = 0; i < k && end; i++) {
            end = end->next;
        }
        if (!end) break;

        // 2. 保存 start 和 next
        struct ListNode* start = pre->next;
        struct ListNode* next = end->next;

        // 3. 断开链表
        end->next = NULL;

        // 4. 反转
        pre->next = reverse(start);

        // 5. 接回链表
        start->next = next;

        // 6. 更新 pre 和 end
        pre = start;
        end = pre;
    }

    return dummy.next;
}

---

🔑 易错点

1. 每轮反转前要重置 end

   end = pre;
   

2. 断开再反转

   • 防止反转后链表丢失下一组节点

   end->next = NULL;
   

3. start 反转后成为尾节点

   • 反转后要接回下一段

   start->next = next;
   

---

时间复杂度

• 每个节点恰好被访问两次（一次找到，一次反转）

• O(n)

空间复杂度

• 仅使用常数指针，O(1)

---

总结

• 利用 dummy 节点 + 双指针处理局部区间是链表题常用模板；

• 注意链表断开和连接；

• 这题是面试中考察链表操作能力和指针细节的经典题目。