使用Fisher-Yates算法打乱链表时偶发节点丢失是什么原因？

核心Bug：重连循环条件写反 #

你代码里的节点重连循环的判断条件完全写反了，这是节点丢失的直接原因：

// 错误写法，k初始值为0，永远不可能大于count-1，循环一次都不会执行
for (int k = 0; k > count - 1; k++) {
    relink(array[k], array[k + 1]);
}

重连逻辑完全未执行的情况下，你只是把数组里的节点指针顺序打乱了，但节点本身的next指针还保留着之前循环链表的指向，只有当打乱后的数组顺序刚好和原链表的指向顺序匹配时才不会丢节点，其他时候都会出现节点缺失的问题，你之前把链表改成循环结构只是掩盖了段错误，没有解决根本问题。

修复方案 #

把重连循环的判断条件改为正确的k < count - 1即可：

// 修复后的重连循环
for (int k = 0; k < count - 1; k++) {
    relink(array[k], array[k + 1]);
}

其他优化建议 #

• 不要在shuffle函数内调用srand48(time(NULL))，随机数种子只需在程序启动时初始化一次即可，若短时间内多次调用shuffle，相同的时间种子会导致洗牌结果完全一致。
• 提前把链表改成循环结构的操作可以删除，所有节点已经完整存入数组，只要重连逻辑正确，不会出现野指针访问的问题。

修复后完整代码 #

linked_node* shuffle(linked_node* head) {
    // 空链表直接返回
    if (head == NULL) return NULL;

    int count = 0;
    linked_node* count_head = head;
    while (count_head != NULL) {
        count++;
        count_head = count_head->next;
    }

    #ifdef DEBUG 
        fprintf(stderr, "count: %i\r\n", count);
    #endif

    linked_node** array = malloc(count * sizeof(linked_node*));

    int i = 0;
    linked_node* add_head = head;
    for (i = 0; i < count; i++) {
        array[i] = add_head;
        add_head = add_head->next;
    }

    // srand48(time(NULL)); 移到程序初始化位置调用

    for (int j = count - 1; j > 0; j--) {
        int random = lrand48() % (j+1);
        array_swap(&array[j], &array[random]);
    }

    // 修复重连逻辑
    for (int k = 0; k < count - 1; k++) {
        relink(array[k], array[k + 1]);
    }

    linked_node* new_head = array[0];
    // 保持循环链表结构
    array[count - 1]->next = new_head;

    free(array);
    return new_head;
}

static inline void relink(linked_node* prev, linked_node* next) {
    if (prev != NULL && next != NULL) {
        prev->next = next;
    }
}

void array_swap(linked_node** a, linked_node** b) {
    linked_node* temp = *a;
    *a = *b;
    *b = temp;
}

内容的提问来源于stack exchange，提问作者Dotz0cat