c - 如何随机打乱 C 中的链表

Question

我有一个链表，我想实现一个函数:

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

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

Answer 1

我会推荐朴素的方法:

1. 构建指向每个节点的指针数组。
2. 打乱数组。这比随机化链接结构要容易得多。
3. 通过按数组顺序遍历节点来“重新串接”列表。

当然，这会使用相对较少的额外内存，但我认为，与直接在链表上工作的方法相比，它在实现(和理解)时间以及可能还有运行时方面更“高效”。