• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

02-线性结构3 Reversing Linked List

浙大mooc 站点默认 1个月前 (11-04) 13次浏览 已收录 0个评论

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
​​ ) 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组数据为一组然后将这组数据翻转过来。值得注意的是,题目给我们的结点不是顺序的,需要我们后续把他们连起来,题意大概就是这么个题意了。

思路:先看看输出,简单利落,就是将翻转后的结点输出,当然前面是它自己的地址,后面是下一个结点的地址。我们首先想到的应该是用连链表的结构来做。但是要知道,我们的链表结构体的一个结点,在我们申请后就已经自动给我们分配了一个内存地址,这与题意的模拟地址不符,那我起码得扩充结构体申请三个数据位。但是这样做又是画蛇添足了。所以,只需要申请两个数组模拟链表就好了


#include<iostream>
#include<stdio.h>
#define  max 100008
using namespace std;
int main(){
	int data[max];
	int next[max];
	int list[max];
	int firstnode , n ,k ;
	int temnode ,temdata ,temnext;
	cin>>firstnode>>n>>k;
	for(int i=0;i<n;i++){
		cin>>temnode>>temdata>>temnext;
		data[temnode]=temdata;
		next[temnode]=temnext;
	}
	//接下来从题给我们的头结点,把结点给理顺,之前说了给的结点不是顺序关系,理顺后我们再对其反转
	 int sum=0;
	 while(firstnode!=-1){
	 	list[sum++]=firstnode;
	 	firstnode=next[firstnode];
	}
	for(int i=0;i<sum-sum%k;i+=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\n",list[i],data
    ],list[i+1]); printf("%05d %d -1\n",list[sum-1],data
      ]); return 0; }

      个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
      转载请注明原文链接:02-线性结构3 Reversing Linked List
      喜欢 (2)
      []
      分享 (0)
      发表我的评论
      取消评论

      表情 贴图 加粗 删除线 居中 斜体 签到