2019牛客国庆集训派对 双向链表练习题 解题报告
双向链表练习题
https://ac.nowcoder.com/acm/contest/1099/K
链接
解题思路
这是一道模拟题。要求不断地让一个列表追加到另一个列表中，并反转。但是不停反转是很耗性能的，不停地反转将会导致超时。为了解决这个反转超时问题，我们开两个表，一个正向表，一个反向表。把正向表与反向表的元素对调一下，就相当于反转了。这样就不会超时了。
+-----------+
| 开始 |
+-----------+
|
|
|
|
v
+---------------------------------+
| 建两个链表，一个正向表，一个反向表 |
+---------------------------------+
|
|<-------------------------------+
| |
v |
+-------------+ |
| 输入追加操作 | |
+-------------+ |
| |
| |
| |
v |
+------------------------+ |
| 对正向表执行追加操作，即 | |
| 正向表La += Lb | |
+------------------------+ |
| |
| |
| |
v |
+---------------------------------+ |
| 对反向表倒过来执行逆向追加操作，即 | |
| 反向表Lb += La | |
+---------------------------------+ |
| |
| |
| |
v |
+-------------------------------------+ |
| 把这两个表的刚变的两个元素对调一下，即 | |
| swap(正La, 反Lb) | |
+-------------------------------------+ |
| |
| |
v |
+-------------------------------+ |
| 把反向表的元素放到正确的位置，即 | |
| swap(反La, 反Lb) | |
+-------------------------------+ |
| |
| |
| |
v |
X |
X XXX |
XXX XXX |
XXXX XXXX 有 |
XXXX 还有下个操作吗？ XX+------------------+
XX XXX
XX XXX XX
XXXXXX XX
XXXX X X
XX
|
| 无
|
v
+-------------------+
| |
| 输出正向表的L1元素 |
| |
+-------------------+
|
|
|
|
|
v
+---------+
| 结束 |
+---------+源代码
#include <cstdio>
#include <list>
#include <algorithm>
using namespace std;
#define MAX_LENGTH 100001
int main()
{
int n, m;
static list<int> plist[MAX_LENGTH];
static list<int> plist_reverse[MAX_LENGTH];
while (scanf("%d%d", &n, &m) != EOF)
{
for (int i = 1; i <= n; ++i)
{
plist[i].clear();
plist[i].push_back(i);
plist_reverse[i].clear();
plist_reverse[i].push_back(i);
}
while (m --)
{
int a, b;
scanf("%d%d", &a, &b);
plist[a].splice(plist[a].end(), plist[b]);
plist_reverse[b].splice(plist_reverse[b].end(), plist_reverse[a]);
swap(plist[a], plist_reverse[b]);
swap(plist_reverse[a], plist_reverse[b]);
}
printf("%d", (int)(plist[1].size()));
for (int e : plist[1])
printf(" %d", e);
puts("");
}
return 0;
} 
