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

1、需要注意的是如果剩余的链表的节点个数小于k，那么就不用翻转了 2、使用堆栈，每次压入k个，然后对里面的进行翻转，翻转简单，但是连接有点麻烦，这也是本题的唯一难点，就是连接，解决了连接问题答案呼之欲出了 3、如何连接，首先初始化一个哑节点，这个节点的next是指向空的，因此第一遍我们直接判断它是否为空，为空才将第一次翻转后的新的头节点连接上去，这样就获得了最终的头节点。 3、后面的连接套路和上面一样，但是哑节点我们就不能动了，他已经处理好了，此时我们建立另外一个临时的节点，一样的操作，每次保存翻转后的最后一个节点，翻转前判断它是否为空，为空说明还没有翻转过，所以不处理，如果已经翻转了一段，那么此时它就存储了翻转后那一段的最后一个位置，我们保存起来，等下一段翻转后，再将它指向下一段翻转后的新的头节点

1 2 3 4 5 6 7 8 ,假设k = 3

初始：此时设置pre_old = nullptr

一轮翻转后: 3 2 1 | 4 5 6 7 8, 此时pre_old = 1

第二轮翻转前：由于使用的是堆栈，栈顶的就是接下来的新一段的头节点，直接将pre_old先指向它即可， 1 --> 6;

二轮翻转后：3 2 1 | 6 5 4 | 7 8 此时的pre_old = 4;

剩余的已经不足k个了，直接将pre_old指向cur，后面的保持不变即可；

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

class Solution {

public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k<=1 || !head) return head;
        ListNode* dummy = new ListNode(0);
        ListNode* cur = head, *pre = head, *pre_old = nullptr;
        stack<ListNode*> st;
        int len = 0;
        while(cur){
            cur = cur->next;
            len++;
        }
        if(k>len) return head;
        int cnt = len / k;
        
        cur = head;
        while(cur){
            int idx = k;
            while(cur && idx--){
                st.push(cur);
                cur = cur->next;
            }
            ListNode* tmp = st.top();
            if(!dummy->next) dummy->next = tmp;
            st.pop();
            if(pre_old) pre_old->next = tmp;
            while(!st.empty()){
                tmp->next = st.top();
                tmp = st.top();
                st.pop();
            }
            pre_old = tmp;
            if(!cur) pre_old->next = nullptr;
            if(--cnt == 0){
                pre_old->next = cur;
                break;
            }
        }
        return dummy->next;
    }
};