Pat class B 1025 reverse linked list

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(<= 10⁵)、 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 33218

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