如何在C中随机混洗链表

我有一个链表，我想实现一个function：

Random_Shuffle_List (struct node **Headptr) – 输出一个列表，使每个节点从其原始位置随机移动。

请帮我一个有效的算法来实现这一目标。

Answer 1

我会推荐天真的方法：

1. 构建指向每个节点的指针数组。
2. 洗牌arrays。 这比随机化链接结构更容易。
3. 通过逐步执行数组顺序中的节点来“重新线程化”列表。

当然，这会占用相对较少的额外内存，但我认为它在实现（和理解）时间方面比在链接列表上直接工作的方式更有效。

Answer 2

简单地反转链表，并交换中间节点和结束节点。我认为这将工作。复杂性将是O（n）。

Answer 3

1. 计算链表中的节点数，比如n
2. 生成0和n之间的两个随机整数（ a ， b ）
3. 交换两个节点a和b 。
4. 重复上面几次m次。

这不是一个好方法，但不需要额外的内存作为@ unwind的建议。

@ unwind的解决方案是使用一个窗口，可以做一件事。

1. 修复一个窗口长度w
2. 在链表中选择两个随机节点，使得可以形成3个长度为w （窗口）的两个非重叠子列表
3. 构建两个数组，每个数组用于指向列表中每个音符的一个窗口
4. 洗牌每个窗口
5. 两个窗口之间的随机指针
6. 重新链接节点
7. 进行上述窗口选择，洗牌和重新连接m次。