题目描述

题目链接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

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

思路解析

        在遍历链表的同时，记录节点数以及开始、结束翻转的位置，当节点数为k时翻转这k个节点，在翻转完k个节点之后将翻转后的k个节点放回元链表中。

翻转链表图解：

更新start、end图解：

        其中第一行为第一次翻转前的位置，第二行为第一次翻转完的位置，第三行为end、start修改完指向的位置，第四行为第二次翻转前的位置。

代码实现

class Solution {
public:
    void reve(ListNode*start,int k){
        ListNode*l = nullptr,*r = start->next;
        while(k--){//利用两个辅助指针翻转该组节点
            start->next = l;
            l = start;
            start = r;
            if(r->next)r = r->next;
        }
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k==1)return head;//如果一个为一组的话不需要翻转直接返回
        ListNode*p,*h = new ListNode();//p用来遍历节点，h为虚头节点
        h->next = head;
        p = h;
        ListNode*start,*end = h;//start记录开始翻转的节点，end记录翻转段中的最后一个节点
        int cnt = 0;//计数
        while(p&&p->next){//遍历链表
            p = p->next;
            cnt++;
            if(cnt == 1)start = p;//当计数为1时记录该节点
            if(cnt == k){//当计数为k时旋翻转k个节点
                ListNode*n = p->next;//提前记录p的next节点
                reve(start,k);//翻转
                end->next = p;//将翻转完的节点拼接回原来的节点
                start->next = n;
                end = start;//更新end、p节点以及cnt
                p = start;
                cnt = 0;
            }
        }
        return h->next;
    }
};