1025 反转链表（附详细注释，逻辑分析）

写在前面

• 实现思路
  • 结构体封装数据
    • 根据order重新排序
    • k区间值迭代翻转
      • n整除k，则最后地址输出"-1"
      • 非整除，最后剩余区间，原序输出。最后地址输出"-1"
• 题目有难度，区间边界值、实现方案费时间

测试用例

input:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

ac代码

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 100010;
struct Node // 定义静态链表
{
    int address, data, next;
    int order;
    Node()
    {
        order = maxn;
    }
} node[maxn];
bool cmp(Node a, Node b)
{
    return a.order < b.order;
}
int main()
{
    int bgin, n, k, address;
    scanf("%d%d%d", &bgin, &n, &k);  // 存储地址、节点个数、步长（步骤1）
    for(int i=0; i<n; i++)
    {
        scanf("%d", &address);
        scanf("%d%d", &node[address].data, &node[address].next);
        node[address].address = address;
    }

    int p = bgin, cnt = 0;
    while(p !=-1 )  // cnt 有效节点个数（步骤2）
    {
        node[p].order = cnt++;
        p = node[p].next;
    }
    sort(node, node+maxn, cmp);

    n = cnt;
    for(int i=0; i<n/k; i++)  // 枚举完整的n/k块
    {
        // 第i块倒序输出（步骤3）
        for(int j=(i+1)*k-1; j>i*k; j--)
            printf("%05d %d %05d\n", node[j].address, node[j].data, node[j-1].address);
        // 每块最后一个节点地址处理
        printf("%05d %d ", node[i*k].address, node[i*k].data);

        // 非最后一块，指向下一块的最后一个节点（步骤4）
        if(i<n/k-1) printf("%05d\n", node[(i+2)*k-1].address);
        else  // 最后一块
        {
            if(n%k==0) printf("-1\n");  // 最后一个节点，输出-1;否则，打印剩余不完整的块相应节点（步骤5）
            else
            {
                printf("%05d\n", node[(i+1)*k].address);
                for(int i=n/k*k; i<n; i++)
                {
                    printf("%05d %d ", node[i].address, node[i].data);
                    if(i<n-1) printf("%05d\n", node[i+1].address);
                    else printf("-1\n");
                }
            }
        }
    }

    return 0;
}

学习代码

• 1025. 反转链表 (25).cpp···墙裂推荐···
• 实现思路
  • 3个整型数组，有效节点地址顺序lists、节点数据data、下一节点地址next
  • 翻转地址，打印输出数据、地址、下一地址即可
  • 根据翻转后的地址循环打印结果数据
  • 打印最后节点
  • 思想很巧妙,值得学习！

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int first, k, n, temp;
    cin >> first >> n >> k;
    int data[100005], next[100005], list[100005];
    for (int i = 0; i < n; i++) {
        cin >> temp;
        cin >> data[temp] >> next[temp];
    }
    int sum = 0;//不一定所有的输入的结点都是有用的，加个计数器
    while (first != -1) {
        list[sum++] = first;
        first = next[first];
    }
    for (int i = 0; i < (sum - sum % k); i += k)
        reverse(begin(list) + i, begin(list) + i + k);
    for (int i = 0; i < sum - 1; i++)
        printf("%05d %d %05d\n", list[i], data[list[i]], list[i + 1]);
    printf("%05d %d -1", list[sum - 1], data[list[sum - 1]]);
    return 0;
}

知识点小结

// 区间翻转函数
reverse(begin(list) + i, begin(list) + i + k);