[pat题解]1074.Reversing Linked List(25)

本题要求对一个链表进行分组逆置,给定K,每K个元素为一组,将组中元素逆置,如果最后一组元素不足K个,则不做处理。
本题个人做法为使用map来组织链表结构,可以方便的进行查询和处理。

c++代码如下: 

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>


using namespace std;

map<int, int> ne;
map<int, int> keys;
vector<int> lists;

void reverse(int l, int r)
{
	while (l < r)
	{
		int t = lists[l];
		lists[l] = lists[r];
		lists[r] = t;
		++l, --r;
	}
}

int main()
{
	int add, key, theNext, head, n, k;

	scanf("%d %d %d", &head, &n, &k);

	for (int i = 0; i < n; ++i)
	{
		scanf("%d %d %d", &add, &key, &theNext);
		ne[add] = theNext;
		keys[add] = key;
	}

	while (head != -1)
	{
		lists.push_back(head);
		head = ne[head];
	}

	n = lists.size();
	for (int i = 0; i < n; i += k)
	{
		if (i + k <= n)reverse(i, i + k - 1);
	}
	lists.push_back(-1);

	
	for (int i = 0; i < n; ++i)
	{
		printf("%05d %d", lists[i], keys[lists[i]]);
		if (lists[i + 1] == -1)printf(" -1\n");
		else printf(" %05d\n", lists[i + 1]);
	}
	return 0;
}

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[pat题解]1074.Reversing Linked List(25)

本文链接地址:http://www.iaccepted.net/algorithm/pat/112.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注