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

/**

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

/* 能想到的没有新意的做法

1.先计算原链表有多少个节点； 2.该链表有多少组子链表需要反转； 3.每反转一次，头结点都指向反转后链表的头结点，并遍历到该子链表的尾节点； 4.最后链接剩余未反转的第一个节点； */

class Solution { public: /** * * @param head ListNode类 * @param k int整型 * @return ListNode类 / / 旋转begin到end */ ListNode * reverse(ListNode *begin) { if (!begin) { return begin; } ListNode *pre = nullptr, *curr = begin; while(curr) { ListNode *next = curr->next; curr->next = pre; pre = curr; curr = next; } return pre; }

// 统计个数
int calListCnt(ListNode* head) {
    ListNode *root = head;
    int cnt = 0;
    while(root) {
        cnt++;
        root = root->next;
    }
    return cnt;
}
ListNode *getEnd(ListNode* head, int k) {
    ListNode *root = head;
    while(--k) {
        root = root->next;
    }
    return root;
}
ListNode* reverseKGroup(ListNode* head, int k) {
    if (!head) {
        return head;
    }
    if (k == 1) {
        return head;
    }
    int cnt = calListCnt (head);
    int circle = cnt / k;
    
    if (circle == 0) {
        return head;
    }
    
    ListNode *ret = new ListNode(-1);
    ListNode *temp = ret;
    ListNode *next, *start = head;
    
    while(circle--) {
        // 获取head之后的k个节点
        ListNode *end = getEnd(start, k);
        // 保存end的next
        next = end->next;
        // 切断关系
        end->next = nullptr;
        // reverse head 和 end
        ListNode * rev = reverse(start);
        // 开始拼接
        temp->next = rev;
        int tempNum = k;
        while(tempNum--) {
            temp = temp->next;
        }
        // 重新定义开始
        start = next;
    }
    
    temp->next = next;

    return ret ->next;
}

};