K个一组翻转链表

• 模拟
  • 设置虚拟头结点
  • （当待翻转部分尾元素的下一个元素不为空时）循环的每次翻转K个元素
    • 确定待翻转部分的前驱结点，然后根据前驱结点确定待翻转部分的首结点、尾结点、后继结点。
    • 翻转待翻转部分（虚拟头结点+待翻转部分）
    • 翻转后利用确定的四个结点将翻转部分与前面的已翻转部分和后面的未翻转部分连接起来。
    • 更新前驱结点，重置尾结点。（尾结点是重置后的尾结点（==前驱结点）K次循环确定的）
  • 如果根据前驱结点K次循环确定的待翻转部分尾结点为null，说明剩下元素不足K个，直接返回。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *dummy = new ListNode();  // 虚拟头结点
        dummy->next = head;
        ListNode *pre = dummy;  // 前驱结点
        ListNode *end = dummy;  // 尾结点 每次重置为dummy，便于K次循环确定dummy。
        while (end->next != NULL) {  // 尾结点的下一个结点为NULL->刚好翻转完整个链表
            // 通过前驱结点确定待翻转部分的首尾结点、后继结点
            ListNode *start = pre->next;
            for (int i = 0; i < k && end != NULL; i++) end = end->next;                
            if (end == NULL) break;  // 如果end为空，说明剩下元素不足K个，直接返回
            ListNode *next = end->next;
            end->next = NULL;  // reverse结束的条件
            // 通过四个结点将刚翻转完的部分和前面已翻转的部分、后面未翻转的部分连接起来
            pre->next = reverse(start);
            start->next = next;
            // 更新前驱结点、清空尾结点。
            pre = start;
            end = pre;
        }
        return dummy->next;
    }
    ListNode *reverse(ListNode *node) {
        ListNode *pre = NULL;
        ListNode *cur = node;
        while (cur != NULL) {
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};