欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

天梯赛练习——7-2 Reversing Linked List (25分)

程序员文章站 2022-06-07 21:44:28
...

题目:

天梯赛练习——7-2 Reversing Linked List (25分)

分析:

首先,看明白要求,题目要求的是:每 k 个元素进行逆转,也就是说如果 k < n/2的话需要逆转多次。
其次,题目中可能出现多条链,只需要输出需要的链即可

下面的代码中应用了 algorithm 库中的 reverse 函数,用于逆转元素,详情代码如下:

代码:

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

const int MAXN = 1e5+5;
int ad,n,k,ind;
int num[MAXN];

struct node
{
    int val,nex;
}no[MAXN];

int main()
{
    int add,val,nex;
    scanf("%d%d%d",&ad,&n,&k);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d%d",&add,&val,&nex);
        no[add].val = val;
        no[add].nex = nex;
    }
    int st = ad;
    while(st!=-1)
    {
        num[ind++] = st;
        st = no[st].nex;
    }
    int indx = 0;
    while(indx+k<=ind) //这里应该是小于等于 因为 indx+k不参与reverse
    {
        reverse(num+indx,num+indx+k);
        indx = indx + k;
    }
    for(int i=0;i<ind-1;++i)
        printf("%05d %d %05d\n",num[i],no[num[i]].val,num[i+1]);
    printf("%05d %d -1\n",num[ind-1],no[num[ind-1]].val);
    return 0;
}

相关标签: # 天梯赛