I have been working on a project. Part of the project needs a shuffled linked list. This function is an implementation of the fisher-yates shuffling algorithm. It puts the linked list into an array. Then it shuffles it. Then relinks it.
After some testing I have found that sometimes when I shuffle a linked list, I lose a node somewhere. I have done some testing with ubsan and asan. They both show nothing. I used to have a issue with this function causing a segfault later on. The segfault was causing by not relinking the linked list correctly. More specifically the last node before shuffling in the linked list was not relinked correctly. I fixed that somewhat by making the list circular before shuffling it.
Here is the code used for shuffling along with the swap and relink functions:
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;
}
There is a typo in this for loop
It seems you mean
Also this statement
is redundant and actually does not have an effect. Remove it.
This statement
could be substituted for this statement