题解 | #链表中的节点每k个一组翻转#

1、 用栈分组翻转。单次翻转，时间复杂度o(n)，空间复杂度o(k)。

#include<stack>
using namespace std;


class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        stack<ListNode *> stk;
        ListNode dummy = ListNode(0);
        dummy.next = head;
        // 哨兵节点
        ListNode *pre = &dummy;
        while(head != nullptr) {
            int i = 0;
            for(i=0; i<k && head!=nullptr; i++) {
                stk.push(head);
                head = head->next;
            }
            if (i==k) {
                pre->next = stk.top();
                stk.pop();
                ListNode * cur = pre->next;
                while(!stk.empty()) {
                    cur->next = stk.top();
                    stk.pop();
                    cur = cur->next;
                }
                pre = cur;
                // 这里把已翻转区间的右节点和未翻转的左节点连接，让区间不足的情况不用处理
                pre->next = head;
            } else {
                while(!stk.empty()) {
                    stk.pop();
                }
            }
        }
        return dummy.next;
    }
};

2、复用翻转链表前n个节点的能力(实现方法：递归)。每次分组翻转前，有前置的哑节点做定位，调用翻转链表前n个节点的函数，再拼接哑节点和翻转后的链表。时间复杂度o(n)，空间复杂度o(k)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k<=1 || head == nullptr) {
            return head;
        }
        int n = 0;
        ListNode* cur = head;
        while(cur != nullptr) {
            n++;
            cur = cur->next;
        }
        ListNode dummy = ListNode(0);
        dummy.next = head;
        ListNode *pre = &dummy;
        while(n>=k) {
            n -= k;
            cur = pre->next;
            ListNode* newHead = reverseNLength(cur, k);
            pre->next = newHead;
            pre = cur;
        }
        return dummy.next;
    }

    ListNode* reverseNLength(ListNode* head, int n) {
        if(n<=1 || head == nullptr) {
            return head;
        }
        ListNode* next = head->next;
        ListNode* newHead = reverseNLength(next, n-1);
        head->next = next->next;
        next->next = head;
        return newHead;
    }
};

1. 复用翻转链表前n个节点的能力（实现方法： 头插法）。增加一个哑节点作为定位。时间复杂度o(n)，空间复杂度o(1)

#include<stack>
using namespace std;


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        stack<ListNode *> stk;
        ListNode dummy = ListNode(0);
        dummy.next = head;
        // 哨兵节点
        ListNode *pre = &dummy;
        while(head != nullptr) {
            int i = 0;
            for(i=0; i<k && head!=nullptr; i++) {
                stk.push(head);
                head = head->next;
            }
            if (i==k) {
                while(!stk.empty()) {
                    ListNode *top = stk.top();
                    stk.pop();
                    pre->next = top;
                    pre = top;
                }
                // 翻转末尾将下一个区间的起始连起来，最后一段不需要翻转的情况就无需处理
                pre->next = head;
            } else {
                while(!stk.empty()) {
                    stk.pop();
                }
            }
        }
        return dummy.next;
    }

};