【牛客】链表中的节点每k个一组翻转(c++实现)

link

题目：

将给出的链表中的节点每\ k k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是\ k k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
要求空间复杂度 \ O(1) O(1)
例如：
给定的链表是$1\to 2\to 3\to 4\to 5$
对于 $k=2$ , 你应该返回$2\to 1\to 4\to 3\to 5$
对于 $k=3$, 你应该返回 $3\to 2\to 1\to 4\to 5$

示例1
输入

{1,2,3,4,5},2

输出

{2,1,4,3,5}

题解：

每隔k个翻转一次，使用tail和start记录每次翻转前,上一段的尾巴节点，和这一段的开始节点；
翻转后，将上次的tail->next打到这次的翻转后的新节点new_head，并更新尾巴节点为这次翻转前的开始节点（翻转后变为尾巴节点）；
注意，由于间隔是k，也就是每一个字段有k个节点，那么我们寻找每次需要翻转的子链表时，指针从开始节点走到尾巴节点需要走k-1步，所以下面代码中 i 的范围是从0到k-2，也就是k-1步；

代码：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        if(head == nullptr || head->next == nullptr || k < 2) return head;
        ListNode* dummy = new ListNode(NULL);
        dummy->next = head;
        ListNode* p = head;
        ListNode* tail = dummy;
        while(p){
            ListNode* start = p;
            bool isend = false;
            for(int i = 0; i < k-1; ++i){
                if(p == nullptr || p->next == nullptr){
                    isend = true;
                    break;
                }
                p = p->next;
            }
            if(isend) break;
            
            ListNode* temp = p->next;
            p->next = nullptr;
            ListNode* new_head = reverseList(start);
            tail->next = new_head; // last tail->next = new head
            tail = start;
            tail->next = temp;
            p = temp;
        }
        
        return dummy->next;
    }
    
    ListNode* reverseList(ListNode* start){
        ListNode* p = nullptr;
        while(start){
            ListNode* temp = start->next;
            start->next = p;
            p = start;
            start = temp;
        }
        return p;
    }
};