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

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

#include <cstdlib>
#include <stack>
class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        // 操作head指针copy版
        ListNode* count=head;
        // 设置哨兵结点，方便返回头结点
        ListNode* _top = new ListNode(0);
        // 头结点是0，其次才是head
        _top->next=head;
        // 操作链表receive，-top会跟着动态变化
        ListNode* receive=_top;
        int number=0;
        bool isEmpty=false;
        stack<int> st;
        stack<int> reverse;
        // st原理是：不断地将head数据放到栈里，当number是k的倍数时，压出数据
        // reverse原理：在while循环里尾部不满足number=N*k的数据也被压入栈里，这里reverse只是将其反转，方便后续操作
        while (!isEmpty && count!=nullptr) {
            st.push(count->val);
            count=count->next;
            number++;
            cout << number << '\t';
            if (number%k==0) {
                while (!st.empty()) {
                    ListNode* temp=new ListNode(0);
                    temp->val=st.top();
                    temp->next=nullptr;
                    receive->next=temp;
                    receive=receive->next;
                    // if (number==k) {
                    //     top->next=receive;
                    // }
                    cout << st.top() << endl;
                    st.pop();
                }
            }
            if (count==nullptr) {
                isEmpty=true;
            }
        }
        // 反转剩下的st
        while (!st.empty()) {
            reverse.push(st.top());
            cout << st.top() << endl;
            st.pop();
        }
        // 将剩下st的结点载入链表
        while (!reverse.empty()) {
            ListNode* temp=new ListNode(0);
            temp->val=reverse.top();
            temp->next=nullptr;
            receive->next=temp;
            receive=receive->next; 
            reverse.pop();
            // free(temp);
        }
        
        return _top->next;
    }
};