一.题目描述
NC50链表中的节点每k个一组翻转
题目链接：
https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=196&&tqId=37080&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
给出一个链表，每 k个节点为一组进行翻转，并返回翻转后的链表。k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么将最后剩余节点保持原有顺序。
示例：
图片说明
二.算法(暴力模拟)
链表操作多复杂，直接用vector可以使代码简化。

  • 遍历一遍链表，把链表的数值全部存到vector里面
  • 每当添加了k个，局部进行一次翻转，利用revserse函数：reverse(左边位置，右边位置)
  • 最后再把数组内的值赋给链表
    下面直接上代码：
    class Solution {
public:
  ListNode* reverseKGroup(ListNode* head, int k) {
      if(k==1) return head;//要是k=1 直接原数组不发生改变
      ListNode *cur=head;//利用一个新指针去更新
      vector<int> v;
      int count=0, index=0;
      while(cur){
          v.push_back(cur->val);
          count++; 
          index++;
          if(count==k){
              //当计数器是k表示链表需要翻转 利用reverse函数翻转
              reverse(v.begin()+index-k, v.begin()+index);
              //计数器清零
              count = 0;
          }
          //指针后移
          cur=cur->next;
      }
      cur=head;
      //最后返回是指针 对指针值进行从新赋值
      for(int i=0;i<v.size();i++){
          cur->val=v[i];
          cur=cur->next;
      }
      return head;
  }
};
    时间复杂度：O(n)
    空间复杂度：O(n)需要开辟vector来存储数
    优缺点：实现简单，但是空间消耗大

三.算法(递归)

图片说明
首先，我们要实现一个reverse函数反转一个区间之内的元素。在此之前我们再简化一下，在给定头节点的情况下对链表进行反转。

// 反转以 a 为头结点的链表
ListNode reverse(ListNode a) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    while (cur != null) {
        nxt = cur.next;
        // 逐个结点反转
        cur.next = pre;
        // 更新指针位置
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

反转以a为头结点的链表其实就是反转a到null之间的结点，那么反转a到b之间的结点就只需要吧null改为b是不是就可以实现了？下面给出反转a到b之间节点的代码:

/** 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    // while 终止的条件改一下就行了
    while (cur != b) {
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

现在我们迭代实现了反转部分链表的功能，那么只需要遍历种反转链表不就是可以了么，下面是完整代码：

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto node=head;
        for (int i=0;i<k;i++) { 
            if (!node) return head;
            node = node->next;
        }
        auto res = reverse(head, node); // 翻转长度是k的链表
        head->next = reverseKGroup(node, k); // 递归处理下一个长度是k的链表
        return res; //返回头指针
    }
private:
    //reverse函数实现反转a到b之间的结点
    ListNode* reverse(ListNode* left, ListNode* right) {
        auto pre=right;
        while (left!=right) {
            auto node=left->next;
            left->next=pre;
            pre = left;
            left = node;
        }
        return pre;
    }
};

时间复杂度:O(n)
空间复杂度:O(1) 没有使用额外空间
优缺点：时间复杂度低，但是思考过程难 不容易向到