How to randomly shuffle a linked list in C?

i need to shuffle a linked list but i dont know how to do it.. please help..

How to randomly shuffle a linked list in C?
I'll first assume that you have a linked list with a head and a tail pointer that point to the first and last element in the linked list, respectively.





The next thing you need to do is have a count of the number of elements in the list. Actually, for this problem, if you don't already, you might want to add this counter to the Insert() and Remove() functions to automatically update this value.





Now, create a loop that executes n-times (n being the number of elements in your list). It could be more or less, your call, but n is a good start. Each iteration of the loop, choose a random value between 2 and the number of elements. Traverse the list to that random element and have a temp pointer point to that element. Then, make the element before it point to the element after it and (if it's a double linked list) making the element after it, point back to the element before it. Make sure you have the temp pointer point to the random element BEFORE cutting it else you'll have lost the address and leaked memory. Now, move the randomly cut element to the head of your list by first having your random element point to the first element in the list. If it's a double-link, have the first element point to the random element. Finally, revise the head pointer to point to the random element.





As I mentioned above, just be careful to always have some pointer pointing to an element your moving so you don't loose the element. In retrospect, you didn't need the tail pointer. However, if you have a really big double-linked list, then you could start from the tail and work up if the random node is closer to the end.