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

Question

我有一个链接列表，我想实现一个功能：

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

请帮助我用一种有效的算法来实现这一点。

Answer 1

我会推荐天真的方法：

1. 建立一个指向每个节点的指针数组。
2. 随机排列数组。这比随机化链接结构更容易。
3. 通过按数组顺序遍历节点来“重新线程化”列表。

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

Answer 2

只需反转链表并交换中间节点和结束节点。我认为这会起作用。复杂度将是 O(n)。

Answer 3

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

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

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

1. 修复say的窗口长度w
2. 选择链表中的两个随机节点，这样可以w形成两个不重叠的3.长度（窗口）的子列表
3. 构建两个数组，每个数组对应一个指向列表中每个音符的窗口
4. 随机播放每个窗口
5. 在两个窗口之间随机播放指针
6. 重新链接节点
7. 执行上述窗口选择、洗牌和重新链接m时间。

Answer 4

一种方法是初始化一个额外的字段，该字段将包含由随机函数生成的随机数。

typedef struct node
{
int data;
int random;
struct node *next;
} card;

for eg, we can give
newnode->random = rand() % (100)  
,which will give random numbers up to 100 to the field.Now Ordering the 
 linked list to ascending or descending according to the random number ,will 
help us to shuffle the nodes .

for (tempnode = start; tempnode->next != NULL; tempnode = tempnode->next)
    for (nextnode = tempnode->next; nextnode->next != NULL; nextnode = 
    nextnode->next)
    {
        if (tempnode->random > nextnode->random)
        {
            swap(tempnode, nextnode);
        }
    }