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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <list>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    //思路：最容易想到的是用栈暴力破解.
    //其次就是把链表按k长度断开，分成一个个小链表，然后使用反转链表，再把它们一一接上，最重要的是应该保存哪些节点
    ListNode* reverse(ListNode* head) 
    {
        if(head == nullptr||head->next == nullptr)
            return head;
	  
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* next = nullptr;

        while (cur!= nullptr )
        {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        if(head == nullptr||k<=1)
        {
            return head;
        }
        ListNode v(-1);
        v.next = head;

        ListNode* pre = &v;//pre是要反小链表首节点的前一个节点
        ListNode* end = &v;//end是每次要反转链表的最后一个节点
        ListNode* start = nullptr;//每次反转之前的首节点
        ListNode* next = nullptr;//反转后end的next会丢失要保存，也是end后的下一个要反转小链表的首节点
        while(1)
        {
            for(int i =0;i<k;i++)//不到k个节点的链表，就不用反转
            {    
                end = end->next;
                if(end == nullptr)//必须得移动后再判断，画图去理解
                {
                    goto label;//跳出所有循环
                }
            }
            
            start = pre->next;
            next = end->next;
            end->next = nullptr;//切断与其他小链表的联系,不然后面调用reverse()返回不理想的结果

            pre->next = reverse(start);//pre的next永远指向每个翻转后的新链表首节点
            start->next = next;//此时start是反转链表的最后一个节点，要让它指向下一次要反转小链表的首节点，不然就要丢失下一个小链表了
            pre = start;//换到下一个要反转小链表的首节点前一个结点
            end = start;
            
        }
        label:
        return v.next;
    }
};