题解 | #将单链表的每K个节点之间逆序#

#include <iostream>
#include<stack>
#include<vector>
#include<algorithm>
#include<list>
using namespace std;
//链表节点结构体
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){}
};
//初始化插入数据
ListNode* Init() {
    ListNode* head=new ListNode(-1);
    ListNode* tmp=head;
    int n;
    int x;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        ListNode* newNode = new ListNode(x);
        tmp->next = newNode;
        tmp = tmp->next;
    }
    return head->next;
}
//打印链表
void PrintList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
}

class Solution {
public:
    Solution() {
    }
    ListNode* reverseK(ListNode* head, int k) {
        stack<int> s;
        int count = 0;
        ListNode* cur = head;
        ListNode* res = new ListNode(-1);
        ListNode* rescur = res;
        while (cur != nullptr) {
            count++;
            s.push(cur->val);
            if (count == k) {
                while (count!=0) {
                    count--;
                    ListNode* newNode = new ListNode(s.top());
                    s.pop();
                    rescur->next = newNode;
                    rescur = rescur->next;
                }
            }
            cur = cur->next;
        }
        while (!s.empty()) {
            ListNode* newNode = new ListNode(s.top());
            newNode->next = rescur->next;
            rescur->next = newNode;
            s.pop();
        }
        return res->next;
    }
    
};

int main() {
    Solution s;
    ListNode* p = Init();
    int k;
    cin >> k;
    ListNode* res = s.reverseK(p, k);
    PrintList(res);    
    return 0;
}