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

用yummyhead的非递归方法，先获取每组元素，如果够k个元素就反转。反转通过头插法来实现。

class Solution {
public:
/*
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode reverseKGroup(ListNode* head, int k) {
// write code here
// 每k个一组，进行反转

    if (k == 0 || k == 1) return head;
    ListNode *yummyhead = new ListNode(-1);  // 设置伪头结点保证循环操作的一致性
    yummyhead->next = head;
    ListNode *p = yummyhead, *q = nullptr, *cur = yummyhead;  // cur指向每一段的最后一个结点
    while (cur->next) {
        int i = 0;

        for (; i < k && cur->next; i++) {  // 虽然只有一个元素，但还是够跳两次
            cur = cur->next;  // 循环退出时，cur指向第k个位置才可啊，以上两种表达结果是一样的，都是先next在++
            // 跳k-1下，得到长度为k的链表
        }  // 循环后，cur指向的该组的最后一个结点

        if (i == k) {
            // 说明该组够k个元素，则反转
            q = cur->next;  // 让后继指针指向后继节点，防止断链
            cur->next = nullptr;  // 让该组的最后一个结点和后续结点断链，用于后续的反转链表操作

        // 反转前需要记录子链表的第一个结点，反转后该结点将成为子链表的尾结点，与后边链表链接
            ListNode *tmp = p->next;
            // 反转
            p->next = reverse(p->next);  // 将子链表反转，并将上一组组尾元素指向他
            p = tmp;
            tmp->next = q;
            cur = tmp;
        }

    }

    return yummyhead->next;

}

ListNode* reverse(ListNode *head) {
    // 实参指针是复制来了的副本
    // 用头插法实现反转，即遍历链表的每一结点，将其插入到新链表的表头
    ListNode *yummyhead = new ListNode(-1);
    // ListNode *cur = yummyhead->next;
    ListNode *tmp = nullptr;
    while(head) {
        tmp = head->next;  // 记录后续结点，防止断链
        head->next = yummyhead->next;  // 在这里正好将头插的第一个结点的next置空
        yummyhead->next = head;
        head = tmp;  // 相当于遍历指针后移
    }
    return yummyhead->next;
}

};