데이터 구조 02 - 선형 구조 3 리 버스 링 링크 목록

제목.
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 (≤10​ 5 ^5 5​​ ) 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
분석 하 다.
제목 은 한 조 의 형식 에 Address data next 의 결점 을 주 는 것 이다. 요구 에 따라 역순 출력 을 먼저 관찰 하고 역순 후에 변 하지 않 는 곳 은 앞의 두 조 의 데이터 이다. 즉, 모든 결점 의 Address 와 data 는 변 하지 않 고 계속 관찰 하 는 것 이다. 사실은 현재 결점 의 next 는 다음 결점 의 address 이다. 우 리 는 address 와 data 를 저장 하고 그들의 관 계 를 나타 내 는 것 을 고려 해 야 한다.배열 Data [address] = data 를 사용 할 수 있 습 니 다. 마찬가지 로 next 와 Address 도 이런 형식 으로 저장 할 수 있 습 니 다. 즉, next [address] = next 는 address 를 통 해 우 리 는 data [] 배열 을 통 해 대응 하 는 data 를 찾 을 수 있 고 next [] 배열 을 통 해 대응 하 는 next 를 찾 아 저장 한 후에 우 리 는 전체 링크 를 '정리' 할 수 있 습 니 다.제 시 된 first node 는 첫 번 째 address 입 니 다. next [first node] 는 다음 노드 의 address 입 니 다. 한 배열 list [] 로 매번 만 나 는 address 를 기록 합 니 다. 여기까지 우 리 는 address 에 따라 다른 데 이 터 를 찾 을 수 있 는 관계 배열 도 있 고 address 를 순서대로 기록 할 수 있 는 배열 도 있 습 니 다. 문 제 는 '반전 링크' 에서 '반전 Address' 로 간략화 합 니 다.K 개의 노드 를 구간 으로 하여 list [] 배열 에 저 장 된 Address 를 반전 시 키 고 address 와 다른 데이터 의 관계 에 따라 링크 를 완전 하 게 출력 할 수 있 습 니 다!

#include
#include
#define MaxSize 100005
using namespace std;
int main(){
	int Data[MaxSize];
	int Next[MaxSize];
	int list[MaxSize];
	int FirstAdd,N,K;
	scanf("%d %d %d",&FirstAdd,&N,&K);
	for(int i=0;i<N;i++){
		int tmpAdd,tmpData,tmpNext;
		scanf("%d %d %d",&tmpAdd,&tmpData,&tmpNext);
		Data[tmpAdd] = tmpData;
		Next[tmpAdd] = tmpNext;
	}
	int sum=0;   //         
	while(FirstAdd!=-1){   //       -1     
		list[sum++] = FirstAdd;   //     Address
		FirstAdd = Next[FirstAdd];  //        
	}
	for(int i=0;i<sum-sum%K;i+=K){  //   K         
		for(int j=0;j<K/2;j++){  //     
			int t = list[i+j];
			list[i+j] = list[i+K-j-1];
			list[i+K-j-1] = t; 
		}
	}
	for(int i=0;i<sum-1;i++)
		printf("%05d %d %05d
",list[i],Data[list[i]],list[i+1]);
	printf("%05d %d -1
",list[sum-1],Data[list[sum-1]]);
	return 0;
}