给定一个常数 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 ( ≤ 1 0 5 ≤10^5 ≤105?? )、以及正整数 K ( ≤ N ≤N ≤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
首先读入数据存入unordered_map,从头节点开始依次找到所有有效节点,存入向量。遍历向量,节点进入双端队列,每满k个,逆序存放人新的向量,最后未满k个的节点正序存放。按照格式输出lists向量。
#include <bits/stdc++.h>
using namespace std;
struct node
{
int address;
int value;
int next;
};
struct no
{
int address;
int value;
};
vector<node> nodes;
unordered_map<int, node> ump;
deque<node> deq;
vector<no> lists;
int main()
{
int first_address;
int node_num;
int k;
cin >> first_address >> node_num >> k;
for (int i = 0; i < node_num; i++)
{
node n;
cin >> n.address >> n.value >> n.next;
ump.insert(pair<int, node>(n.address, n));
}
node n;
n.address = first_address;
n.value = ump[first_address].value;
n.next = ump[first_address].next;
nodes.push_back(n);
while (n.next != -1)
{
n.address = n.next;
n.value = ump[n.address].value;
n.next = ump[n.address].next;
nodes.push_back(n);
}
ump.clear();
for (int i = 0; i < nodes.size();)
{
for (int j = 0; j < k; j++)
{
node x = nodes[i];
deq.push_back(x);
i++;
if (i == nodes.size())
break;
}
if (deq.size() == k)
{
while (deq.size() != 0)
{
no y;
y.address = deq.back().address;
y.value = deq.back().value;
lists.push_back(y);
deq.pop_back();
}
}
}
while (deq.size() < k && deq.size())
{
no y;
y.address = deq.front().address;
y.value = deq.front().value;
lists.push_back(y);
deq.pop_front();
}
for (int i = 0; i < lists.size(); i++)
{
if (!i)
{
printf("%05d %d ", lists[i].address, lists[i].value);
}
else
{
printf("%05d\n%05d %d ", lists[i].address, lists[i].address, lists[i].value);
}
}
printf("-1");
return 0;
}
unordered_map
头文件: #include < unordered_map >
unordered_map内部实现了一个哈希表(也叫散列表,通过把关键码值映射到Hash表中一个位置来访问记录,查找的时间复杂度可达到O(1),其在海量数据处理中有着广泛应用)。因此,其元素的排列顺序是无序的。
一、简介 本设计为硬币图像识别统计装置通过数码相机获取平铺无重叠堆积的硬币的...
今日国内领先的智能数据服务运营商觉非科技完成近亿元A轮融资。本轮融资由和高资...
首先给扑克牌中每张牌设定一个编号,下面算法实现的编号规则如下: u 红桃按照从...
本文实例讲述了jsp中page指令用法。分享给大家供大家参考。具体如下: 一、JSP ...
git工作区,暂存区,版本库之间的关系: 我们建立的项目文件夹就是工作区,在初...
从功能测试、性能测试、界面测试、安全性测试、易用性、兼容性测试、震动测试七...
一、MVC MVC模式的意思是,软件可以分成三个部分。 视图(View):用户界面。 控...
我们知道微软将会在今年给Windows10更换全新设计的UI,让Windows10的界面更加整...
前言 关于Window,你了解多少呢?看看下面这些问题你都能答上来吗。 如果你遇到这...
大家好,今天我们来简单的聊一聊缓存问题。什么是缓存呢?它在系统设计中是在一个...