摘要
Title: 1110 区块反转
Tag: 单链表
Memory Limit: 64 MB
Time Limit: 1000 ms

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;
}

1110 区块反转

题意

思路

代码