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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @param k int整型
 * @return ListNode类
 */
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    if (k == 1 || head == NULL) {  //间隔为1，顺序不改变，直接返回；空链也直接返回
        return head;
    }
    int i = 1;  //用于计数
    struct ListNode* left = head;  //当前待排区间的第一个结点
    struct ListNode* right = head;  //当前待排区间的最后一个结点
    struct ListNode* cur = head;  //当前待插入结点
    struct ListNode* pre = NULL;  //上一个被插入结点
    struct ListNode* nex = head;  //下一个带插入结点
    struct ListNode* pre_tail = NULL;  //上一段区间的尾结点
    struct ListNode* first = NULL;  //整个链表重排之后的第一个结点

    for (i = 1; i < k && right != NULL; i ++) {  //划分出第一个待排区间
        right = right->next;
    }
    if (right == NULL) {  //第一个待排区间结点个数小于k，直接返回原链表
        return head;
    } else {  //第一个待排区间结点个数不小于k
        first = right;  //标记重排后链表第一个结点
        pre = right->next;  //便于找下一个区间的位置
        for (i = 1; i <= k; i ++) {  //将待排区间重排，采用头插法
            nex = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nex;
        }
        pre_tail = left;  //标记第一个区间的尾结点
        left = left->next;
        right = left;
    }

    while (right != NULL) {  //当链表未重排完成时，循环
        for (i = 1; i < k && right != NULL; i ++) {  //找到待排区间
            right = right->next;
        }
        if (right != NULL) {  //当重排未完成
            pre = right->next;
            for (i = 1; i <= k; i ++) {  //头插法重排区间
                nex = cur->next;
                cur->next = pre;
                pre = cur;
                cur = nex;
            }
            pre_tail->next = right;  //将该区间连接到前面排好的链表之后
            pre_tail = left;  //标记该区间的尾结点
            left = left->next;  //找到下一个区间
            right = left;
        } else {
            pre_tail->next = left;  //该区间节点个数小于k，无需重排
        }
    }
    return first;  //返回重排链表的第一个结点
}
/*
1.没有将第一个区间单独处理，导致程序段出错，因为pre_tail->next使用错误，此时pre_tail==NULL，没有next。单独处理第一段还有一个用处，就是标记好first。
2.nex的处理，最开始是直接让nex=head->next,然后先头插法插入结点后，再nex=nex->next，也是跟第一个问题一样，会碰到nex=NULL,nex->next不存在的情况。
3.没有在当前区间重排之前，标记好后边的链表，这样会导致找不到后边的链表，在重排之前，将pre设置为right->next即可。