题目主要信息:

  • 给定一个链表，从头开始每k个作为一组，将每组的链表结点翻转
  • 组与组之间的位置不变
  • 如果最后链表末尾剩余不足k个元素，则不翻转，直接放在最后

具体思路:

现在我们想一想，如果拿到一个链表，想要像上述一样分组翻转应该做些什么？首先肯定是分段吧，至少我们要先分成一组一组，才能够在组内翻转。然后是组内翻转吧，翻转完了再连接起来。分组很容易，只要每次遍历k个元素，就是一组，翻转即指定区间内的翻转，也很容易，可以参考链表指定区间内的翻转，但是连接的时候遇到问题了：首先如果能够翻转，链表第一个元素一定是第一组，它翻转之后就跑到后面去了，而第一组的末尾元素才是新的链表首，我们要返回的也是这个元素，而原本的链表首要连接下一组翻转后的头部，即翻转前的尾部，如果不建立新的链表，看起来就会非常难。

但是如果我们从最后的一个组开始翻转，得到了最后一个组的链表首，是不是可以直接连在倒数第二个组翻转后的尾（即翻转前的头）后面，是不是看起来就容易多了。怎样从后往前呢？我们这时候可以用到自上而下再自下而上的递归或者说栈。接下来我们说说为什么能用递归？如果这个链表有nn个分组可以翻转，我们首先对第一个分组翻转，那么是不是接下来将剩余n−1n-1个分组翻转后的结果接在第一组后面就行了，那这剩余的n−1n-1组就是一个子问题。我们来看看递归的三段式模版：

  • 终止条件： 当进行到最后一个分组，即不足k次遍历到链表尾（0次也算），就将剩余的部分直接返回。
  • 返回值： 每一级要返回的就是翻转后的这一分组的头，以及连接好它后面所有翻转好的分组链表。
  • 本级任务： 对于每个子问题，先遍历k次，找到该组结尾在哪里，然后从这一组开头遍历到结尾，依次翻转，结尾就可以作为下一个分组的开头，而先前指向开头的元素已经跑到了这一分组的最后，可以用它来连接它后面的子问题，即后面分组的头。

具体过程可以参考如下：

alt

代码实现:

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* tail = head; //找到每次翻转的尾部
        for(int i = 0; i < k; i++){ //遍历k次到尾部
            if(tail == NULL) //如果不足k到了链表尾，直接返回，不翻转
                return head;
            tail = tail->next; 
        }
        ListNode* pre = NULL; //翻转时需要的前序和当前节点
        ListNode* cur = head;
        while(cur != tail){ //在到达当前段尾节点前
            ListNode* temp = cur->next; //翻转
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        head->next = reverseKGroup(tail, k); //当前尾指向下一段要翻转的链表
        return pre;
    }
};

复杂度分析：

  • 时间复杂度：O(n)O(n)，一共遍历链表nn个结点
  • 空间复杂度：O(n)O(n)，递归栈最大深度为n/kn/k