当前位置:网站首页>Pat class B 1025 reverse linked list
Pat class B 1025 reverse linked list
2022-06-23 05:58:00 【Octopus bro】
1025. Reverse a linked list (25)
Given a constant K And a single linked list L, Please write a program to L Every time K Node inversion . for example : Given L by 1→2→3→4→5→6,K by 3, Then the output should be 3→2→1→6→5→4; If K by 4, Then the output should be 4→3→2→1→5→6, That is, less than K Elements do not invert .
Input format :
Each input contains 1 Test cases . Each test case is No 1 Line gives 1 The address of the node 、 The total number of nodes is a positive integer N(<= 105)、 And positive integers K(<=N), That is, the number of child chain nodes requiring inversion . The address of the node is 5 Bit nonnegative integer ,NULL Address use -1 Express .
Next there is N That's ok , The format of each line is :
Address Data Next
among Address Is the node address ,Data Is the integer data saved in this node ,Next Is the address of the next node .
Output format :
For each test case , Output the inverted linked list in sequence , Each node on it occupies a row , The format is the same as the input .
sample input :00100 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218sample output :
00000 4 33218 33218 3 12309 12309 2 00100 00100 1 99999 99999 5 68237 68237 6 -1
Ideas : The data element of this operation is a containing address 、 data 、 The structure of the next node address , Apply for one first 100001 Array of structures of , Using dynamic memory allocation , Directly declare the array in dev Overflow in . Take the array subscript as the address , Each time you input a node, you will find the subscript position corresponding to the address and save it . After storing all nodes , In the order of the linked list ( That is, start from the address of the first node , Until I met -1 end ) After sorting, it is stored in another array , Finally, in the ordered array K In reverse order . Be careful , Answer: the Lord got the card at the last test point long long time!! Finally, it is found that the test case contains nodes that are not in the linked list ~,~
So when you meet next by -1 Exit input when .
One 、 Starting variable
1.input[100001], The node used to save the input
2.sortQ[100001], It is used to save the sequence arranged according to the linked list sequence
3.add The address of the first node in the linked list
4.N Number of nodes
5.K Number of subsequences
Two 、 Algorithm
1. Enter all nodes
2. take input The nodes in the are placed in the order of addresses sortQ In sequence ;
3. Invert the nodes in the subsequence
4. Modify the of each node after the last reverse order next And the output
3、 ... and 、 Code
#include "stdio.h"
#include "stdlib.h"
typedef struct{
int address;// Address
int data;// data
int next;// Next node address
}node;
int main()
{
node * input = (node *)malloc(sizeof(node) * 100001);// The node used to store the input
node * sortQ = (node *)malloc(sizeof(node) * 100001);// Used to store ordered nodes
int add,N,K;
scanf("%d %d %d",&add, &N, &K);// Input starting variable
//1. Input node
for(int i = 0; i < N; i++)
{
node tmp;
scanf("%d %d %d",&tmp.address, &tmp.data, &tmp.next);
input[tmp.address] = tmp;
}
//2. take input The nodes in the are placed in the order of addresses sortQ In sequence ;
for(int i = 0; i < N; i++)
{
sortQ[i] = input[add];
add = input[add].next;
// The last test point is to add this if Later through , That is, change as soon as the end is met N Out of the loop
// If it is not added, you will access the node that has not stored data , There will be errors in the reverse order
if(add == -1)
{
N = i + 1;
break;
}
}
int converseNum = N / K;// The number of subsequences to reverse
//3. Invert the nodes in the subsequence
for(int i = 0; i < converseNum; i++)
{
for(int j = 0; j < K / 2; j++)
{
node tmp = {0, 0, 0};
tmp = sortQ[i * K + j];// The first i( from 0 Start ) The... In the subsequence j And the penultimate j Exchange
sortQ[i * K + j] = sortQ[i * K + K - 1 - j];
sortQ[i * K + K - 1 - j] = tmp;
}
}
//4. here sortQ The nodes in are already inverted sequences , Just modify the of each node next
int i = 0;
for(i = 0; i < N - 1; i++)// Before modifying and exporting n-1 Nodes
{
sortQ[i].next = sortQ[i + 1].address;
printf("%05d %d %05d\n",sortQ[i].address,sortQ[i].data,sortQ[i].next);
}
sortQ[i].next = -1;// Of the last node next by -1
printf("%05d %d %d\n",sortQ[i].address,sortQ[i].data,sortQ[i].next);
return 0;
}
边栏推荐
- Wireshark TS | 视频 APP 无法播放问题
- 编址和编址单位
- Adnroid activity screenshot save display to album view display picture animation disappear
- Explicability of counter attack based on optimal transmission theory
- PAT 乙等 1016 C语言
- PAT 乙等 1023 组个最小数
- Dolphin scheduler dolphin scheduling upgrade code transformation -upgradedolphin scheduler
- Adnroid activity截屏 保存显示到相册 View显示图片 动画消失
- Use of visdom
- Visual Studio调试技巧
猜你喜欢

True question of MySQL interview (29) -- case - finding favorite movies

数字藏品——新的投资机遇

HierarchyViewer工具找不到 HierarchyViewer位置

The hierarchyviewer tool cannot find the hierarchyviewer location

jvm-04.对象的内存布局

ant使用总结(一):使用ant自动打包apk

How to specify the output path of pig register Project Log

Addressing and addressing units

The construction of digital factory can be divided into three aspects

True MySQL interview question (24) -- row column exchange
随机推荐
最优传输理论下对抗攻击可解释性
Activity startup mode and life cycle measurement results
The performance of nonstandard sprintf code in different platforms
[proteus simulation] Arduino uno+pcf8574+lcd1602+mpx4250 electronic scale
Leetcode topic analysis add binary
Pat class B 1019 C language
Pat class B 1026 program running time
android Handler内存泄露 kotlin内存泄露处理
Oracle exception
Pat class B 1022 d-ary a+b
数字藏品如何赋能经济实体?
【owt】owt-client-native-p2p-e2e-test vs2017构建 6:修改脚本自动生成vs工程
Real MySQL interview questions (XXVI) -- didi 2020 written examination questions
使用链表实现两个多项式相加和相乘
The 510000 prize pool invites you to participate in the competition -- the second Alibaba cloud ECS cloudbuild developer competition is coming
【Cocos2d-x】截图分享功能
Jvm: when a method is overloaded, the specific method to call is determined by the static type of the incoming parameter rather than the actual type of the parameter
True MySQL interview question (XXII) -- condition screening and grouping screening after table connection
MySQL character set
PAT 乙等 1011 C语言