我有重排N个长度为n的单链表第一个元素，随意。每个元素被定义为：

I have to permute N first elements of a singly linked list of length n, randomly. Each element is defined as:

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

我有一个根元素，我可以遍历大小为n的整个链表。什么是最有效的技术，仅重排N个第一要素（从根开始）随机？

I have a root element and I can traverse the whole linked list of size n. What is the most efficient technique to permute only N first elements (starting from root) randomly?

因此​​，考虑到A-> B-> C-> D-> E-> F - > ... X-> Y-> Z I需要做出不便。像F-> A-> E-> C-> B - > ... X-> Y->以Z

So, given a->b->c->d->e->f->...x->y->z I need to make smth. like f->a->e->c->b->...x->y->z

我的具体情况：

更新：我发现this纸。它指出它presents邻算法（log n）的堆栈空间和预期为O（n log n）的时间。

UPDATE: I found this paper. It states it presents an algorithm of O(log n) stack space and expected O(n log n) time.

推荐答案

我还没有尝试过，但你可以使用一个随机的合并排序。

I've not tried it, but you could use a "randomized merge-sort".

要更precise，你随机的合并 -routine。你不合并两个子列表系统，但你做的基础上掷硬币（即用概率0.5选择第一个子表的第一个元素，概率0.5您选择合适的子表的第一个元素）。

To be more precise, you randomize the merge-routine. You do not merge the two sub-lists systematically, but you do it based on a coin toss (i.e. with probability 0.5 you select the first element of the first sublist, with probability 0.5 you select the first element of the right sublist).

这应该在运行为O（n log n）的和使用 O（1）空间（如果实施得当）。

This should run in O(n log n) and use O(1) space (if properly implemented).

下面你可以看到在C中的示例实现，你可能会适应你的需求。注意，此实现使用随机在两个地方：在 splitList 和合并。但是，您可能只选择这两个地方之一。我不知道如果分布是随机的（我几乎可以肯定它不是），但一些测试用例取得像样的成绩。

Below you find a sample implementation in C you might adapt to your needs. Note that this implementation uses randomisation at two places: In splitList and in merge. However, you might choose just one of these two places. I'm not sure if the distribution is random (I'm almost sure it is not), but some test cases yielded decent results.

#include <stdio.h>
#include <stdlib.h>

#define N 40

typedef struct _node{
  int value;
  struct _node *next;
} node;

void splitList(node *x, node **leftList, node **rightList){
  int lr=0; // left-right-list-indicator
  *leftList = 0;
  *rightList = 0;
  while (x){
    node *xx = x->next;
    lr=rand()%2;
    if (lr==0){
      x->next = *leftList;
      *leftList = x;
    }
    else {
      x->next = *rightList;
      *rightList = x;
    }
    x=xx;
    lr=(lr+1)%2;
  }
}

void merge(node *left, node *right, node **result){
  *result = 0;
  while (left || right){
    if (!left){
      node *xx = right;
      while (right->next){
    right = right->next;
      }
      right->next = *result;
      *result = xx;
      return;
    }
    if (!right){
      node *xx = left;
      while (left->next){
    left = left->next;
      }
      left->next = *result;
      *result = xx;
      return;
    }
    if (rand()%2==0){
      node *xx = right->next;
      right->next = *result;
      *result = right;
      right = xx;
    }
    else {
      node *xx = left->next;
      left->next = *result;
      *result = left;
      left = xx;
    }
  }
}

void mergeRandomize(node **x){
  if ((!*x) || !(*x)->next){
    return;
  }
  node *left;
  node *right;
  splitList(*x, &left, &right);
  mergeRandomize(&left);
  mergeRandomize(&right);
  merge(left, right, &*x);
}

int main(int argc, char *argv[]) {
  srand(time(NULL));
  printf("Original Linked List\n");
  int i;
  node *x = (node*)malloc(sizeof(node));;
  node *root=x;
  x->value=0;
  for(i=1; i<N; ++i){
    node *xx;
    xx = (node*)malloc(sizeof(node));
    xx->value=i;
    xx->next=0;
    x->next = xx;
    x = xx;
  }
  x=root;
  do {
    printf ("%d, ", x->value);
    x=x->next;
  } while (x);

  x = root;
  node *left, *right;
  mergeRandomize(&x);
  if (!x){
    printf ("Error.\n");
    return -1;
  }
  printf ("\nNow randomized:\n");
  do {
    printf ("%d, ", x->value);
    x=x->next;
  } while (x);
  printf ("\n");
  return 0;
}