如何在C中随机混洗链表

San*_*ngh 0 c algorithm list data-structures

我有一个链接列表,我想实现一个功能:

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

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

unw*_*ind 14

我会推荐天真的方法:

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

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