浙江财经大学
信息管理与工程学院

PAT(B) 1025. 反转链表 (25)

本文由 Ocrosoft 于 2016-12-26 16:50:39 发表

给定一个常数K以及一个单链表L,请编写程序将L中每K个结点反转。例如:给定L为1→2→3→4→5→6,K为3,则输出应该为3→2→1→6→5→4;如果K为4,则输出应该为4→3→2→1→5→6,即最后不到K个元素不反转。

输入格式:

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 105)、以及正整数K(<=N),即要求反转的子链结点的个数。结点的地址是5位非负整数,NULL地址用-1表示。

接下来有N行,每行格式为:

Address Data Next

其中Address是结点地址,Data是该结点保存的整数数据,Next是下一结点的地址。

输出格式:

对每个测试用例,顺序输出反转后的链表,其上每个结点占一行,格式与输入相同。

输入样例:

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

输出样例:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
这题简直…

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define rep(a,v,b) for(int a=v;a<b;a++)
#define repe(a,v,b) for(int a=v;a<=b;a++)
#define pre(a,v,b) for(int a=v;a>b;a--)
#define pree(a,v,b) for(int a=v;a>=b;a--)
#define lowbit(x) x&-x
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 27 + 10;
const int MOD = 1000000007;
int gcd(int a, int b)
{
	if (!b)return a;
	return gcd(b, a%b);
}
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕) 签订契约,成为马猴烧酒吧 (◕‿‿◕)*/
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
using namespace std;
struct node
{
	int add;
	int data;
	int next;
};
int main()
{
	vector<node> vin(100000);
	vector<node> vsorted;
	vector<node> vout;
	node temp;
	int first, N, K;

	scanf("%d%d%d", &first, &N, &K);

	for (int i = 0; i < N; i++)
	{
		scanf("%d%d%d", &temp.add, &temp.data, &temp.next);
		vin[temp.add] = temp;
	}
	if (first == -1)printf("-1\n");
	else
	{
		int nextAdd = first;
		while (nextAdd != -1)
		{
			vsorted.push_back(vin[nextAdd]);
			nextAdd = vin[nextAdd].next;
		}
		int Nnew = vsorted.size();
		int right = K - 1;
		while (right < Nnew)
		{
			for (int i = right; i > right - K; i--)
				vout.push_back(vsorted[i]);
			right += K;
		}
		for (int i = right - K + 1; i < Nnew; i++)
			vout.push_back(vsorted[i]);
		for (int i = 0; i < Nnew - 1; i++)
		{
			vout[i].next = vout[i + 1].add;
			printf("%05d %d %05d\n", vout[i].add, vout[i].data, vout[i].next);
		}
		printf("%05d %d %d\n", vout[Nnew - 1].add, vout[Nnew - 1].data, -1);
	}
	return 0;
}

欢迎分享与转载,请保留链接与出处。Ocrosoft » PAT(B) 1025. 反转链表 (25)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址