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

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

#include <iterator>
class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    void Reverse(ListNode* ps_,ListNode* pe_)
    {
        if(ps_==pe_)
        {
            return;
        }
        else 
        {
            ListNode* t1,* t2,*temp;
            t1=ps_;
            t2=t1->next;
            while(t2!=pe_)
            {
                temp=t2->next;
                t2->next=t1;

                t1=t2;
                t2=temp;
            }
            if(t2==pe_)
            {
                t2->next=t1;
            }
        }
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        if(head==nullptr)
        {
            return nullptr;
        }


        ListNode* newNode=new ListNode(*head);
        newNode->next=head;


        ListNode* ps=newNode;
        ListNode* pe=ps;


        ListNode* ps_=ps->next;
        ListNode* pe_=ps_;//pe_到ps_为需要交换的区间
        int i=1;
        while(pe!=nullptr)
        {
            while(i<k&&pe_!=nullptr)//移动到须要交换的位置
            {
                pe_=pe_->next;
                ++i;
            }
            if(i==k&&pe_!=nullptr)//如果移动成功
            {
                pe=pe_->next;
                Reverse(ps_,pe_);//实现反转连接
                ps_->next=pe;
                ps->next=pe_;


                //恢复为一般状态
                i=1;
                ps=ps_;
                ps_=pe;
                pe_=ps_;
                pe=ps;

            }
            if(pe_==nullptr)//如果到达末尾数量仍然不足
            {
                break;
            }

        }
        return newNode->next;
    }
};

对于一般情况：

......x->a->b->.....->c->y.....

如果逆置要a,b,c可以设置函数 void Reverse(ListNode* ps_,ListNode* pe_)

输入时ps_指向a,pe_指向c

执行结束后

<?....a<-b-<-....<-c（<?....表示不关心指向）

此时需要将x与c相连接，a与y相连接 ,为了防置结点丢失，在执行 Reverse(ListNode* ps_,ListNode* pe_)前应该设置ps,pe,分别指向x,y;

设置ps_=ps->next; pe_=ps_(因为要交换的结点至少为1），调用Reverse（ps_,pe_)

再连接即可。

注意：1.连接完成后需要将ps_,pe_,ps,pe置于一般问题状态

2.注意在寻找区间时如果pe_==nullptr时，表明数量不足k个，由题意应该不进行操作（结束程序）

总结：链表的调整改变结点的指向，指向结点的指针本身是不变的，pe指向结点a,无论链表做了什么调整，pe始终指向a