相关疑难解决方法(0)

我必须随机地置换长度为n的单链表的N个第一个元素.每个元素定义为:

typedef struct E_s
{
  struct E_s *next;
}E_t;

我有一个根元素,我可以遍历整个大小为n的链表.什么是随机排列N个第一个元素(从根开始)最有效的技术？

因此,给定a-> b-> c-> d-> e-> f - > ... x-> y-> z我需要制作smth.像f-> a-> e-> c-> b - > ... x-> y-> z

我的具体案例:

• nN相对于n约为20%
• 我有限的RAM资源,最好的算法应该使它到位
• 我必须在循环中进行多次迭代,因此速度很重要
• 理想的随机性(均匀分布)不是必需的,如果它"几乎"是随机的,那就没关系
• 在进行排列之前,我已经遍历了N个元素(用于其他需求),所以也许我也可以将它用于排列

更新:我发现了这篇论文.它声明它提出了一个O(log n)堆栈空间和预期的O(n log n)时间的算法.