Shuffling a linked list

I have a class that is essentially a pseudo library. The driver creates a NoviceLibrary that can do various things like adding books to the library (ListNode nodes), deleting books, etc.

ShuffleBooks () is the very last function I have to write. Everything else works and can add / remove books. This function should place the nodes in the linked list in a random order. I cannot use the tail pointer that I have seen in other algorithms. I cannot use arrays. I thought I wrote that there are pointers p1 and p2 that swap the nodes in the list. The program stops and gives me no useful information in the log.

void shuffleBooks (int bookCount)
      int r1 = rand() % bookCount;
      int r2 = rand() % bookCount;

      ListNode *p1 = head;
      ListNode *p2 = head;

      // Here I am trying to get the swap to happen 4 times the bookCount
      for (int i = 0; i < bookCount*4; i++)
         for (int i = 0; i < r1; i++)
            p1 = p1->next;

         for (int i = 0; i < r2; i++)
            p2 = p2->next;

         swap(p1->bookVal, p2->bookVal);



source to share

1 answer

Very close, but replaces pointers by shuffling the list? For shuffling, we don't need to tie the nodes differently? We must be careful that we don't turn off the list.

Instead of replacing pointers, how about replacing their successors? In terms of randomness, this is equally good. And it makes reconnection easier.

Below is a diagram for one iteration of swap-shuffle.

list: A -> B -> C -> D -> E -> F -> G -> H
r1: 2 (say)
r2: 4 (say)
p1: C
p2: F

swap p1->next (D) and p2->next (G)

  // save pointers
  p1next = p1->next;         // D
  p1nextnext = p1next->next; // E
  p2next = p2->next;         // G
  p2nextnext = p2next->next; // H

  // relink
  p1->next = p2next;         // C -> G
  p2next->next = p1nextnext; // G -> E
  p2->next = p1next;         // F -> D
  p1next->next = p2nextnext; // D -> H

list: A -> B -> C -> G -> E -> F -> D -> H

Real code need to be careful not to dereference a null pointer.


We can do the previous step k

once to get a nice shuffle. What's the good value k

? I'm not sure, maybe the square root of the length of the list.



All Articles