题目内容

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

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

1、你可以设计一个只使用常数额外空间的算法来解决此问题吗？
2、你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例

示例 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]

示例 3：

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

示例 4：

输入：head = [1], k = 1
输出：[1]

提示

列表中节点的数量在范围 sz 内
1 <= sz <= 5000
0 <= Node.val <= 1000
1 <= k <= sz

题解

本题延续之前上题的思路。

首先需要遍历一次链表，观察给出的用例是否大于k个，只有大于k个才存在翻转的必要。在保证大于k的前提下，我们有如下三个操作。

1、内部元素的反向操作

2、虚拟头结点指向第k个节点的操作

3、原来的实际头结点指向第k个结点的下一个结点的操作

Tips：图中虚线是用于临时指向的指针，防止我们找不到该节点。

然后，每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) {
        //本题首先，需要先遍历一下链表，看其长度是否达到了k个要求。
        //如果达到k的要求，需要进行翻转操作。一共操作分三个部分
        //第一个部分，将内部元素的反向
        //第二个部分，将开头元素指向第k个节点元素
        //第三个部分，将k链表的头节点指向k节点元素的next
        
        auto dummy = new ListNode(-1);
        dummy -> next = head;
        for(auto p = dummy;;){
            auto q = p;
            for(int i = 0; i < k && q; i++) q = q -> next;
            if(!q) break;
            //定义两个节点，最开始节点a指向第一个元素，节点b指向第二个元素
            auto a =  p -> next, b = a -> next;
            //这个for循环对k个几点的内部的边进行反向操作
            for(int i = 0; i < k - 1; i++){
                auto c = b -> next; //首先存储一下b的下一个节点，否则下面覆盖掉就找不到了
                b -> next = a;//翻转方向
                a = b, b = c; //a到b的位置，b到c的位置
            }
            auto d = p -> next;
            p -> next = a;
            d -> next = b; 
            p = d;
        }
        return dummy -> next;
    }
};