c++ - Shuffling a linked list -

i have class pseudo-library. driver creates library novicelibrary can different things, add books library (nodes linked list listnode), remove books, , such , such.

the shufflebooks() last function have write. else works , can add/remove books. function needs put nodes in linked list in random order. cannot use tail pointer, i've seen in other algorithms. can't use arrays. thought had written there pointers p1 , p2 swap nodes in list. program stalls , doesn't give me useful information in log.

void shufflebooks (int bookcount) {       int r1 = rand() % bookcount;       int r2 = rand() % bookcount;        listnode *p1 = head;       listnode *p2 = head;        // here trying swap happen 4 times bookcount       (int = 0; < bookcount*4; i++)       {          (int = 0; < r1; i++)             p1 = p1->next;           (int = 0; < r2; i++)             p2 = p2->next;           swap(p1->bookval, p2->bookval);       } } 

very close, swapping pointers shuffling list? shuffling, don't need link nodes differently? have careful don't disconnect list.

instead of swapping pointers, how swapping successors? randomness perspective, equally good. , makes re-linking easy.

following schematic 1 iteration of swap-shuffle.

list: -> b -> c -> d -> e -> f -> g -> h r1: 2 (say) r2: 4 (say) p1: c p2: f  swap p1->next (d) , 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: -> b -> c -> g -> e -> f -> d -> h  real code need careful not dereference null pointer. 

we can above step k times obtain shuffle. what's value of k? not sure, perhaps square root of list length.