有许多算法可以生成给定值集的所有可能排列。通常，这些值被表示为一个数组，它有O(1)个随机访问。
但是，假设要排列的元素表示为一个双链表。在这种情况下，你不能在O(1)时间内随机访问列表中的元素，因此许多排列算法将经历不必要的减速。是否存在一种算法，以尽可能少的时间和空间开销生成链表的所有可能的排列?
试着想想你是如何在一张纸上生成所有排列的
你从最右边的数字开始，向左移动一个位置，直到你看到一个比它的邻居小的数字。然后你把下一个值的数字放在那里，然后把所有剩下的数字按递增的顺序排列在它之后。这样做，直到无事可做为止。稍微思考一下，你就可以在线性时间内对它们的个数进行排序。
据我所知，这实际上是用于下一个排列的典型算法。
您可能需要查看Steinhaus-Johnson-Trotter算法。它仅通过交换相邻元素来生成序列的所有排列;这在O(1)双链表中是可以做到的
您应该将链表的数据读取到一个数组中，该数组采用O(n)，然后使用Heap的排列(http://www.geekviewpoint.com/java/numbers/permutation)来查找所有的排列。
您可以使用Factoradic Permutation Algorithm，并相应地重新排列节点指针，从而在没有递归的情况下生成相应的排列。
伪描述:
element_to_permute = list
temp_list = new empty list
for i = 1 in n!
indexes[] = factoradic(i)
for j in indexes[]
rearrange pointers of node `indexes[j]` of `element_to_permute` in `temp_list`