25. Reverse Nodes in k-Group

题意

给一个链表和一个数字k，实现每k个节点翻转一次。

思路1

首先明确在这个任务中，有三个部分

• 第一个，将每一块k个节点的链表反转，可以使用递归简单的完成。
• 第二个，之前指向这一块的那个指针现在要指向新的节点了，比如图上，本来指向5的指针要指向7。
• 第三个，本来7是指向下一个块的第一个元素，现在需要5来指向下一块的最后一个元素（因为下一块也需要进行反转）。
  时间复杂度O(n)， 空间复杂度O(k)（递归深度即为所需空间）

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *next, *newhead;//next:下一个k块处理前的首元素,for Task1
                             //newhead:当一个k块处理完了之后，它新的首元素，for Task2 & 3
    ListNode* dfs(ListNode* p, int k)
    {
        if (k == 0)
        {
            next = p->next;//下一次要从新的next处理，在这里更新next，即next是本轮未更新的最后一个节点的next 
            return newhead = p;
        }
        dfs(p->next, k-1)->next = p;//p节点下一个节点的next指向p，完成Task1
        return p;
    }
    ListNode* reverseKGroup(ListNode* head, int k)
    {
        if (!head) return NULL;
        int cnt = 0, i = 1;
        for(ListNode* p = head; p; p = p->next, cnt++);
        ListNode* ret, *pre = NULL, *temp;
        next = head;
        while(i * k <= cnt)
        {
            temp = dfs(next, k-1);//temp是刚处理完的k块新的最后一个节点
            if (!pre) pre = temp;
            else pre->next = newhead, pre = temp;//上次处理完的k块的最后节点指向这一轮k块处理完的新首节点
            if (i == 1) ret = newhead;
            i++;
        }
        if (i != 1) temp->next = next;
        else ret = head;
        return ret;
    }
};

思路2

上述方法不仅又臭又长，还需要O(k)的空间复杂度，显然不太理想。那么使用单链表逆转的思想，逐段反转，最后再完成Task2和3。使用迭代方式，空间复杂度为O(1)。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int cnt = 0, turn = 1;
        for (ListNode* p = head; p ; p=p->next, cnt++);
        ListNode *pre = NULL, *now = head, *next, *newlast = NULL, *ret = head, *st;
        while (turn*k<=cnt)
        {
            st = now;
            for (int i = 0; i < k; i++)
            {
                next = now->next;
                now->next = pre;
                pre = now;
                now = next;
            }
            if (turn == 1) ret = pre, newlast = st;
            else
            {
                newlast->next = pre;
                newlast = st;
            }
            turn++;
            pre = NULL;
        }
        if (newlast) newlast->next = now;
        return ret;
    }
};