CODEWITHSUNDEEP
calgorithmlistdata-structures
Sandeep Singh
Sandeep Singh

Reputation: 5181

How to Randomly Shuffle a Linked List in C

I have a Linked List and I want to implement a function:

Random_Shuffle_List (struct node **Headptr) - which outputs a list such that every single node is randomly moved from its original position.

Please help me with an efficient algorithm to achieve this.

Upvotes: 1

Views: 7688

Answers (4)

Shruti
Shruti

Reputation: 7

one way of doing this is initializing an extra field, that will contain a random number generated by a random function.

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);
        }
    }

Upvotes: -1

acoder
acoder

Reputation: 1085

simply reverse the linked list and and swap the middle node and the end node.I think this will work.complexity would be O(n).

Upvotes: 0

phoxis
phoxis

Reputation: 61910

  1. Count the number of nodes in the linked list, say n
  2. Generate two random integers (a, b) between 0 and n
  3. Swap the two nodes a and b.
  4. Repeat the above some m times.

This is not a good way, but does not require extra memory as @unwind's suggestion.

One thing could be done with @unwind's solution is by using a window.

  1. Fix a window length of say w
  2. Select a two random nodes in the linked list such that two non-overlapping sublists of 3. length w (window) can be formed
  3. Build two arrays, each for one window pointing to each note in the list
  4. Shuffle each window
  5. Shuffle pointers between the two windows
  6. Re link the nodes
  7. Do the above window selection, shuffling and relinking m times.

Upvotes: -1

unwind
unwind

Reputation: 399793

I would recommend the naïve approach:

  1. Build a pointer array pointing at each node.
  2. Shuffle the array. This is way, way easier than randomizing a linked structure.
  3. "Re-thread" the list by stepping through the nodes in the array's order.

This uses a relatively tiny bit of extra memory, of course, but I think it's more "efficient" in terms of time to implement (and understand) and probably also run-time, than approaches working directly on the linked list.

Upvotes: 15

Related Questions