Powered by:NEFU AB-IN

Link

1110 区块反转

• 题意

  给定一个单链表 L，我们将每 K 个结点看成一个区块（链表最后若不足 K 个结点，也看成一个区块），请编写程序将 L 中所有区块的链接反转。例如：给定 L 为 1→2→3→4→5→6→7→8，K 为 3，则输出应该为 7→8→4→5→6→1→2→3。

• 思路

  建立单链表后遍历，将每组的头节点放入vector，并逆序，最后输出即可

• 代码

  /* * @Author: NEFU AB-IN * @Date: 2022-06-04 11:45:48 * @FilePath: \ACM\GPLT\1110.cpp * @LastEditTime: 2022-06-04 12:57:32 */
  #include <bits/stdc++.h>
  using namespace std;
  #define SZ(X) ((int)(X).size())
  #define IOS \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0);
  #define DEBUG(X) cout << #X << ": " << X << endl;
  typedef pair<int, int> PII;
  const int N = 1e6 + 10;
  
  int h, e[N], ne[N];
  int n, k;
  signed main()
  {
        
      IOS;
      cin >> h >> n >> k;
      for (int i = 1; i <= n; ++i)
      {
        
          int addr, data, nxt;
          cin >> addr >> data >> nxt;
          e[addr] = data;
          ne[addr] = nxt;
      }
      vector<int> lst;
      int cnt = 0;
      for (int i = h; ~i; i = ne[i])
      {
        
          if (cnt == 0)
          {
        
              lst.push_back(i);
          }
          cnt += 1;
          if (cnt == k)
              cnt = 0;
      }
      vector<int> ans;
      reverse(lst.begin(), lst.end());
      for (auto addr : lst)
      {
        
          for (int i = addr, cnt = 0; ~i && cnt < k; i = ne[i], cnt++)
          {
        
              ans.push_back(i);
          }
      }
      for (int i = 0; i < SZ(ans); ++i)
      {
        
          if (i != SZ(ans) - 1)
              printf("%05d %d %05d\n", ans[i], e[ans[i]], ans[i + 1]);
          else
              printf("%05d %d -1\n", ans[i], e[ans[i]]);
      }
      return 0;
  }