1 题目

给定一个链表，每 k 个反转一次，不足 k 个不反转。

在 leetcode 上没找到，应该是有的。

2 题解

两次遍历：

第一次获取链表的长度 size，目的是为了第二次遍时的判断剩余元素是否还能支持反转： size - i >= k；

第二次每k个进行反转；

#include <iostream>

template <typename T>
class LinkList {
 public:
  LinkList() : head_(nullptr), tail_(nullptr) {}
  ~LinkList() {
    if (head_ == nullptr) return;

    Node* list = head_;
    while (list) {
      Node* node = list;
      list = list->next;
      delete node;
    }
    head_ = nullptr;
    tail_ = nullptr;
  }

  void reverse_per_k(int k) {
    if (head_ == nullptr) return;

    Node dummy_node;
    dummy_node.next = head_;
    Node *pre = &dummy_node, *cur = head_, *next = nullptr;

    int size = 1;
    Node* node = head_;
    while (node) {
      node = node->next;
      ++size;
    }

    for (int i = 0; size - i >= k; i = i + k) {
      for (int j = 1; j < k; ++j) {
        next = cur->next;
        cur->next = next->next;
        next->next = pre->next;
        pre->next = next;
      }
      pre = cur;
      cur = pre->next;
    }

    head_ = dummy_node.next;
    if (pre->next == nullptr) tail_ = pre;
  }

  void print() {
    if (head_ == nullptr) return;

    Node* list = head_;
    while (list) {
      std::cout << list->data << ' ';
      list = list->next;
    }
    std::cout << std::endl;
  }

  void insert(T value) {
    if (head_ == nullptr) {
      head_ = new Node(value);
      tail_ = head_;
    } else {
      tail_->next = new Node(value);
      tail_ = tail_->next;
    }
  }

 private:
  struct Node {
    T data;
    Node* next;
    Node() : next(nullptr) {}
    Node(T value) : data(value), next(nullptr) {}
  };
  Node* head_;
  Node* tail_;
};

int main() {
  int n = 10;
  LinkList<int> list;

  for (int i = 1; i <= n; ++i) {
    list.insert(i);
  }
  list.print();

  list.reverse_per_k(3);
  list.print();

  return 0;
}