链表优化，优化了63.2%的时间

#include<bits/stdc++.h>
using namespace std;

int n,a[15],nxt[15],pre[15];
inline void write(int x)
{
    if (x>9) write(x/10);
    putchar(x%10+'0');
    return;
}
inline void dfs(int t)
{
	if (t==n+1)
	{
		for (int i=1;i<=n;i++)
			write(a[i]),putchar(' ');
		putchar('\n');
		return;
	}
	for (int i=0;;)
	{
		i=nxt[i];
		if (i>n) break;
		nxt[pre[i]]=nxt[i],pre[nxt[i]]=pre[i],a[t]=i;
		dfs(t+1);
		nxt[pre[i]]=i,pre[nxt[i]]=i;
	}
	return;
}
int main()
{
	cin >> n;
	for (int i=0;i<=n;i++)
		nxt[i]=i+1;
	for (int i=1;i<=n;i++)
		pre[i]=i-1;
	dfs(1);
	return 0;
}