25题：K个一组翻转链表

题目

给你链表的头节点 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]

提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

代码

/**
 * 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) {
        if(head==nullptr || head->next==nullptr)
            return head;
   
        auto reverse_list = [&] (ListNode* head) -> ListNode* {
            ListNode* pre{nullptr};
            ListNode* curr{head};
            ListNode* next{nullptr};
            while(curr)
            {
                next = curr->next;
                curr->next = pre;
                pre = curr;
                curr = next;
            }
            return pre;
        };
       
        ListNode* dumy = new ListNode{0, head};
        ListNode* pre{dumy};
        ListNode* start{head};
        ListNode* end{head};
        ListNode* next{head};
        while(next){
        for(int i=1;i!=k && end!=nullptr;i++)
             end = end->next;
        if(end==nullptr)
            break;
      
        next = end->next;
        end->next = nullptr;
        end = start;
        start = reverse_list(start);
        end->next = next;
        pre->next = start;
        pre = end;
        start = next;
        end = next;
        }
        return dumy->next;

        }
        
  
};

代码简析

这道题其实难道不算过大，主要是思路要理清。我们可以通过画图来理清楚每步的思路。

由于涉及到链表翻转，所以我们需要用一个真“头结点”始终指向第一个节点，也就是 ListNode* dumy = new ListNode{0,head}。这样我们可以用 dumy->next来返回结果。
由题意，我们需要k个为一组。所以我们设定一个 pre指针指向每一组的前一个位置，一个 start指针指向每组第一个位置，一个 end指针指向每组最后一个位置，一个 next指针指向每组结尾的后一个位置。
我们通过一个 while(next)循环来进行 n%k次循环。每次循环前，我们会循环 k-1次，让 end指向每组最后一个数（end每次循环开始时应该是指向每组第一个数，和 start一样）。
如果在 k-1次之前就出现 end==nullptr的情况，说明已经不需要分组了，直接在后面退出循环。接着，我们让 next=end->next指向第一个块的后面一个位置。对于第一块，一般就是下面这种情况。

接下来，我们就要开始做该块的翻转了。我们期望翻转后的结果是 start指向原来最后一个元素，end指向原来的第一个元素。我们需要把这个块单独“截断”出来做翻转。链表方法很简单，我们只要把 end的 next设为空即可。之后我们把这个块传入一个简单的链表翻转函数（这里我们为了简洁，不另外写一个成员函数，而是写了一个lambda表达式）得到翻转后的块。

auto reverse_list = [&] (ListNode* head) -> ListNode* {
            ListNode* pre{nullptr};
            ListNode* curr{head};
            ListNode* next{nullptr};
            while(curr)
            {
                next = curr->next;
                curr->next = pre;
                pre = curr;
                curr = next;
            }
            return pre;
        };

翻转函数同样，我们初始化 curr指向块的起始位置。原理很简单，我们把每个节点的 next指向改为之前的元素即可。这里我们用 pre这个空指针初始化每个节点之前的元素。每次我们保存每个节点原始的 next指向的位置，并将其 next值改为 pre。之后我们把 pre改为现在的节点。然后利用之前保存的 next指针前进 curr。一直到 curr为空，翻转就结束。最后我们返回 pre指针即可。

假如我们翻转了第一个块，我们返回的应该是 2->1->nullptr这个链表的头结点。我们需要重新将这个块“接回”原链表。即用 end->next=next。

我们现在为下一次循环做准备，即让 pre指向该块最后一个节点（也就是下一个块的上一个位置）pre=end。start和 end指向下一个块的初始位置。之后继续循环直到结束就可以成功让这些组逐个翻转。