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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
 /**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
//思路  先求出链表长度，然后/k来求得要逆置的次数，用头插法来达到逆置的效果
 //记得要对一次的操作要特殊处理，同时要有一个prev指针来起到链接的作用
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    struct ListNode* prev = head;
    struct ListNode* cur = head;
    struct ListNode* curnext = head;
    struct ListNode* tmp = head;
    struct ListNode* newhead = NULL;//分别是逆置后的头和尾
    struct ListNode* newtail = NULL;
    int leng = 0;
    int ret = k;
    while (cur)//求链表长度
    {
        cur = cur->next;
        leng++;
    }
    if (leng < k)
    {
        return head;
    }
    int num = leng / k;
    cur = head;
    while (num--)//要逆置的次数
    {
        ret = k;
        
        cur = curnext;
        while (ret--)//为了方便逆置后的头结点与原链表的链接
        {
            curnext = curnext->next;
        }
        while (cur != curnext)
        {
            tmp = cur->next;
            if (newhead == NULL)//头插法第一次逆zhi要特殊处理
            {
                cur->next = curnext;
                newhead = cur;
                newtail = cur;
            }
            else {
                cur->next = newhead;
                newhead = cur;
            }
            cur = tmp;
        }

        if ((num + 1) == leng / k)//对第一次操作要特殊处理
        {
            head = newhead;
            prev = newtail;
        }
        else
        {
            prev->next = newhead;
            prev = newtail;

        }
        newhead = NULL;//记得重置newhead的值
    }
    return head;
}