为什么我在混洗链表时丢失了一个节点？

Question

我一直在做一个项目。项目的一部分需要一个混洗的链表。此函数是fisher-yates混洗算法的实现。它将链表放入数组中。然后它会对它进行洗牌。然后重新链接它。

经过一些测试后，我发现有时当我对链表进行混洗时，我会在某个地方丢失一个节点。我用ubsan和asan做了一些测试。它们都没有显示任何内容。我曾经在这个函数上遇到过一个问题，后来导致了一个段错误。段故障是由于未正确重新链接链表而导致的。更具体地说，链表中混洗之前的最后一个节点没有正确地重新链接。我在混洗列表之前使列表循环，这在一定程度上解决了这个问题。

以下是用于混洗以及交换和重新链接函数的代码：

linked_node* shuffle(linked_node* head) {
    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;
    }
    
    //made circluar to prevent segfault with the last node
    array[count - 1]->next = head;

    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];

    //made circular for ease of use later
    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;
}

Answer 1

此for循环中有一个拼写错误

for (int k = 0; k > count - 1; k++) {
                ^^^^^^^^^^^^^
    relink(array[k], array[k + 1]);
}

看起来你是说

for (int k = 0; k < count - 1; k++) {
                ^^^^^^^^^^^^^
    relink(array[k], array[k + 1]);
}

还有这句话

//made circluar to prevent segfault with the last node
array[count - 1]->next = head;

是多余的，实际上没有效果。去掉它。

这句话

//made circular for ease of use later
array[count - 1]->next = new_head;

可以用来替换此语句

array[count - 1]->next = NULL;