『卡过，递归的优美设计』题解 | #链表中的节点每k个一组翻转#

• 卡过
• 设计递归的启发性思考
• 本身的递归，和辅助函数的调用

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

//返回翻转后的头结点
ListNode * reverseHelp( ListNode * Left, ListNode * Right )
{
    ListNode * sentry=nullptr;
    ListNode * cur=Left;
    while( cur!=Right )
    {
        ListNode * temp=cur->next;
        cur->next=sentry;

        sentry=cur;
        cur=temp;
    }

    return sentry;
}
class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        if( nullptr==head ) return nullptr;
        ListNode * Right=head;
        int loop=k;
        while( loop-- )
        {
            //表示没有k个可以进行翻转了
            if( nullptr==Right ) return head;
            Right=Right->next;
        }
        //temp获得到第k+1的位置
        ListNode * Left=head;

        ListNode * newHead=reverseHelp( Left , Right );
        Left->next=reverseKGroup( Right ,  k);
        return newHead;
    }
};