题目描述

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明：
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

解题思路

找到每组链表节点的头和尾(head、tail)，将这一组节点翻转；
另外，需要保留每组节点的上一个节点(prev、next)，方便接上翻转后的头、尾节点；
对于第一组节点，由于没有prev，需要设定一个虚的prev节点(hair)，另外这样也方便直接返回结果(hair->next)。

pair<ListNode*, ListNode*> helper(ListNode* head, ListNode* tail){
    ListNode* prev = tail->next;
    ListNode* curr = head;

    while(prev!=tail){
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }

    return pair<ListNode*, ListNode*>(tail, head);
}

ListNode* reverseKGroup(ListNode* head, int k){
    ListNode* hair = new ListNode(0);
    hair->next = head;
    ListNode* prev = hair;
    
    while(head){
        ListNode* tail = prev;
        for(int i=0; i<k; i++){
            tail = tail->next;
            if(!tail)
                return hair->next;
        }

        ListNode* nex = tail->next;
        tie(head, tail) = helper(head, tail);

        prev->next = head;
        tail->next = nex;
        prev = tail;
        head = nex;
    }
    
    return hair->next;
}