【OJ】K 个一组翻转链表

题目
基本思路：用计数+栈实现分段，K个一组地翻转链表。

#include <bits/stdc++.h>
#include <stack>
using namespace std;

struct list_node {
  int val;
  struct list_node *next;
};

list_node *input_list() {
  int val, n;
  scanf("%d", &n);
  list_node *phead = new list_node();
  list_node *cur_pnode = phead;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &val);
    if (i == 1) {
      cur_pnode->val = val;
      cur_pnode->next = NULL;
    } else {
      list_node *new_pnode = new list_node();
      new_pnode->val = val;
      new_pnode->next = NULL;
      cur_pnode->next = new_pnode;
      cur_pnode = new_pnode;
    }
  }
  return phead;
}

list_node *reverse_knode(list_node *head1, int K) {
  if (K < 2 || !head1 || !head1->next) {
    return head1;
  }
  std::stack<list_node *> s;
  int cnt = 0;
  int cnt_interval = 0;
  list_node *last_tail = nullptr;
  list_node *cur_head = nullptr;
  list_node *cur = head1;
  list_node *new_head = nullptr;
  while (cur) {
    s.push(cur);
    cnt++;
    cur = cur->next;
    if (cnt == K) {
      cnt = 0;
      cnt_interval++;
      list_node *i_pre = s.top();
      s.pop();
      cur_head = i_pre;
      if (cnt_interval > 1) {
        last_tail->next = cur_head;
      } else {
        new_head = cur_head;
      }
      while (!s.empty()) {
        list_node *i_cur = s.top();
        s.pop();
        i_pre->next = i_cur;
        i_pre = i_cur;
      }
      last_tail = i_pre;
      last_tail->next = cur;
    }
  }
  return new_head;
}

void print_list(list_node *head) {
  while (head != NULL) {
    printf("%d ", head->val);
    head = head->next;
  }
  puts("");
}

int main() {
  list_node *head = input_list();
  int K;
  scanf("%d", &K);
  list_node *new_head = reverse_knode(head, K);
  print_list(new_head);
  return 0;
}

测试，

g++ ./ReverseKNode.cpp
./a.out
5
1
2
3
4
5
2