Перетасовка связанного списка

Question

У меня есть класс, который по существу является псевдо-библиотекой. Драйвер создает библиотеку NoviceLibrary, которая может делать разные вещи, такие как добавление книг в библиотеку (узлы связанного списка ListNode), удаление книг и т. Д.

ShuffleBooks() - это самая последняя функция, которую я должен написать. Все остальное работает и может добавлять/удалять книги. Эта функция должна помещать узлы в связанном списке в случайном порядке. Я не могу использовать указатель на хвост, который я видел в других алгоритмах. Я не могу использовать массивы. Я думал, что я написал, что есть указатели p1 и p2, которые меняют узлы в списке. Программа останавливается и не дает мне полезной информации в журнале.

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

Answer 1

Очень близко, но заменяет указатели, перетасовывая список? Для перетасовки нам не нужно связывать узлы по-разному? Мы должны быть осторожны, чтобы мы не отключали список.

Вместо замены указателей, как насчет замены их наследников? С точки зрения случайности, это одинаково хорошо. И это облегчает повторное соединение.

Ниже приведена схема для одной итерации 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. 

Мы можем сделать вышеописанный шаг, k раз, чтобы получить хорошую перетасовать. Какова хорошая стоимость k? Я не уверен, возможно, квадратный корень из длины списка.