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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* start;ListNode* var=new ListNode(1);//定义一个虚拟头节点
        ListNode* cur=head,*pre=var;stack<ListNode*> Q;//利用栈实现反转
        //pre记录当前反转节点的尾节点
        while(cur)
        {
            start=cur;//记录当前反转的起始节点
            for(int i=0;i<k;i++)//从当前节点入栈k次
            {
                if(cur)Q.push(cur);
                else break;//如果当前节点为空
                cur=cur->next;
            }
            if(Q.size()==k)//如果栈大小为k说明可以逆序
            {
                while(!Q.empty())
                {
                    pre->next=Q.top();Q.pop();
                    pre=pre->next;
                }
            }
            else //后续节点不能逆序
            {
                while(start)//从起始节点连接到逆序链表中去
                {
                    pre->next=start;
                    start=start->next;
                    pre=pre->next;
                }
            } 
        }
        pre->next=nullptr;//新链表尾节点置空
        head=var->next;
        delete var;
        return head;
    }
};