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

struct ListNode* reverse(struct ListNode* head, int k) {

    struct ListNode* cur, *next, *pre;

    pre = NULL, cur = head, next = head->next;

    while (k--) {

        cur->next = pre;

        pre = cur;

        cur = next;

        next = next->next;

    }

    return pre;

}

struct ListNode* reverseKGroup(struct ListNode* head, int k ) {

    // write code here

    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));

    dummyHead->next = head;

    struct ListNode* revHead, *revEnd;

    int count = 0;

    revHead = dummyHead, revEnd = dummyHead->next;  //head表示反转区间前一个节点，end表示反转区间后一个节点

    if (k == 1)                 //如果k=1，则直接返回

        return dummyHead->next;

    while (revEnd) {            //寻找区间节点过程中，如果区间后的节点不存在，则直接退出

        revEnd = revEnd->next;  //存在则指向下一个

        if (++count == k) {     //如果找到一个满足k的区间，则开始反转

            revHead->next = reverse(revHead->next, k); //区间前一个节点的next  为  反转后链表

            while (count--) {   //找到反转后的链表的 区间的末尾节点

                revHead = revHead->next;

            }

            revHead->next = revEnd; //此时head为反转好的区间的末尾节点，next指向之前保存的反转区间的后一个节点，

            //同时revHead处于下一区间的前一个节点。[2 1(head)] [3 4]

            count = 0;            //count置0

        }

    }

    return dummyHead->next;

}