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

使用上一题翻转区间内链表的思路

• 排除各类特殊情况：链表空，链表只有一个，一组节点数大于链表内节点总数
• 之后
• 第一组翻转需要特殊处理，因为它没有前结点
• 之后的所有组都按照：找反转头，反转头的前结点，反转尾，翻转尾的后节点，再按照部分翻转，之后链接翻转部分和原来部分即可

 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param k int整型 
 * @return ListNode类
 */

 
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    // write code here
    //遍历获得链表节点个数
    int list_count=0;
    struct ListNode* count_head=head;
    while(count_head){
        count_head=count_head->next;
        list_count++;
    }
    //如果空链表，或者链表只有一个元素，或者反转一组链表节点个数小于k，直接返回链表头
    if(head==NULL || head->next ==NULL || list_count<k){
        return head;
    }
    struct ListNode* node=head;
    struct ListNode* org_head=head;
    struct ListNode* org_head_pre=NULL;
    int count=1;
    while(count<=list_count){
        if(count==k){
            struct ListNode* org_tail=node;
            struct ListNode* org_tail_next=node->next;
            //原地反转法将需要反转的部分链表反转
            struct ListNode* pre=org_tail_next;
            struct ListNode* cur=org_head;
            struct ListNode* next=cur->next;
            while(cur!=org_tail_next){
                cur->next=pre;
                pre=cur;
                cur=next;
                next=next->next;
            }
            head=pre;//保存一下整个链表的头结点
        } 
        if(count%k==0 && count>k){
            //遍历寻找此次反转的头
            int count_m=1;
            struct ListNode* org_head=head;
            while(count_m<count-k+1){
                org_head=org_head->next;
                count_m++;
            }
            //寻找此次反转头的前一个
            struct ListNode* org_head_pre=head;
            int count_m2=1;
            while(count_m2<count-k){
                org_head_pre=org_head_pre->next;
                count_m2++;
            }
            //找到反转的尾
            int count_n=1;
            struct ListNode* org_tail=head;
            while(count_n<count){
                org_tail=org_tail->next;
                count_n++;
            }
            //找到反转尾的下一个节点
            int count_n2=1;
            struct ListNode* org_tail_next=head;
            while(count_n2<=count){
                org_tail_next=org_tail_next->next;
                count_n2++;
            }
            //原地反转法将需要反转的部分链表反转
            struct ListNode* pre=org_tail_next;
            struct ListNode* cur=org_head;
            struct ListNode* next=cur->next;
            while(cur!=org_tail_next){
                cur->next=pre;
                pre=cur;
                cur=next;
                next=next->next;
            }
            org_head_pre->next=pre; //链接翻转部分和原来的部分
        }
        node=node->next;
        count++;
    }
    return head;
}