题目链接：https://vjudge.net/problem/UVA-11988
题目大意：输入一个字符串，输出在原本应该是怎么样的？ 具体方法是 碰到' [ ' 回到最前面 碰到‘ ]’ 回到最后面。
思路：很容易可以想到用数组来写，但是仔细分析一下，每次你把一个字符插入到最前面，它后面的字符全都要往后移，那么复杂度是多大呢？ 最差的情况，每一个都插在最前面，呢么复杂度是
n*n 肯定超时的。 应用链表则只有n的复杂度了。 这是我接触到的第一道链表题目，说的详细一点：
比如 abcde 如果你要在ab 之间插入f 那么你首先把f的后继改为a的后继，a的后继改为f 这就插入完成了 其实这就是核心了。 但是为了方便 我们通常设置一个头结点 [0] 从1开始存数据：
下面看代码：
#include<iostream>
#include<string.h>
#include<vector>
#include<stdio.h>
using namespace std;
const int maxn=1e5+;
int main()
{
char a[maxn];
int next[maxn];
while(scanf("%s",a+)!=EOF)//存在s[1] s[2]~~~~中
{
int len=strlen(a+);//保存在s[1] s[2]~~~~中
int cur=;//光标在的位置 下次插入在光标所在位置后面一位
int last=;//最后一位所在的位置
next[]=;//初始化
for(int i=;i<=len;i++)//遍历一遍
{
char c=a[i];
if(c=='[') cur=;//光标调到最前面
else if(c==']') cur=last;//光标调到最后面
else
{
next[i]=next[cur];//这两个操作就是节点的插入
next[cur]=i;
if(cur==last) last=i;//更新最后一个字符的编号
cur=i;//光标移动
}
}
for(int i=next[];i!=;i=next[i]) printf("%c",a[i]);//按照链表输出
printf("\n");
}
return ;
}