当前位置：首页 > news >正文

1074 Reversing Linked List (25)

news 来源：原创 2025/5/7 3:16:25

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤105) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

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

Sample Output:

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

题目大意：给出一个静态链表，将链表每k个节点逆转，若不足k个则不逆转。输出逆转后的链表。

分析：先依次将节点存入一个数组中，每进来k个节点，就逆转一次，直到遍历完整个链表。输出时下一个地址即为排在后一个的元素地址。
注意：不一定所有的输入的结点都是有用的。

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include   <string>
#include   <vector>
#include   <cstdio>
#include    <queue>
#include    <stack>
#include    <ctime>
#include    <cmath>
#include      <map>
#include      <set>
#define INF 0xffffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
using namespace std;typedef struct node
{int add,data,next;
}node;int main(void)
{#ifdef testfreopen("in.txt","r",stdin);//freopen("in.txt","w",stdout);clock_t start=clock();#endif //testint ss,n,k;scanf("%d%d%d",&ss,&n,&k);node num[100000];node ans[n+5];for(int i=0;i<n;++i){int a,b,c;scanf("%d%d%d",&a,&b,&c);num[a].add=a,num[a].data=b,num[a].next=c;}int temp=ss,t=0,sum=0;while(temp!=-1){ans[sum]=num[temp];sum++;if(sum%k==0&&k!=1)for(int i=sum-k,j=sum-1;i<j;++i,--j)swap(ans[i],ans[j]);temp=num[temp].next;}for(int i=0;i<sum;++i){printf("%05d %d ",ans[i].add,ans[i].data);if(i!=sum-1)printf("%05d\n",ans[i+1].add);else printf("-1\n");}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl;        //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位#endif //testreturn 0;
}

Input Specification:

Output Specification:

Sample Input:

Sample Output:

相关文章：