Linked List shuffling

Every programmer should know what a linked list is, here is brief a description from wikipedia:

In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.

In this post I want write how to shuffle linked list.

In a very simple way when you are shuffling array you can make it in two steps:

1. for every index you can generate some random index - time complexity is O(N)
2. swap corresponding elements. - time complexity is O(1)

This algorithm works in O(N) time, where N is size of array.

Let's try to implement this approach for our linked list. first step is the same, but second one isn't as easy as it seems. In linked list you can't access elements by index, therefore you must iterate whole list and examine all elements. This takes N operation and you would get O(N*N) complexity.

My aim is to show you another algorithm, which will work in O(N LogN) time.

In my algorithm I'm using Divide and Conquer approach.

1. divide list into halves
2. reshuffle both lists
3. merge reshuffled list.

This algorithm works in O(N*LogN), because list will be divided LogN times and complexity of merging is O(N). Here is my implementation of this algorithm:

 #include <cstdlib>
#include <cstdio>
#include <ctime>
using namespace std;
//list item
struct Item{
Item* next; // pointer to the next element in list
int value; // value of element
Item(){
  next = NULL;
}
};
int Min(int a, int b){
return a<b?a:b;
}
//construction list
Item* constructList(int N){
Item* root = new Item();
Item* t = root;
t->value = 0;
for(int i = 1; i < N; i++) {
  t->next = new Item();
  t = t->next;
  t->value = i;
  }
return root;
}
//root = first element of list
//len = length of list
void shuffle(Item* root, int len){
if(len==1) return; //if len==1 than there is nothing to shuffle
Item* r2 = root;
//splitting list,  get first element of second list r2
int i = 0;
while(i < len/2) r2 = r2->next,i++;
//shuffle first list
shuffle(root, len/2);
//shuffle second list
shuffle(r2, len-len/2);
//merging lists
for(int i = 0; i < Min(len/2, len - len/2); i++){
  if(rand()%2) {
        //swap values of two element
        int value = root->value;
        root->value = r2->value;
        r2->value = value;
  }
  //goto next element
  root = root->next;
  r2 = r2->next;
}
}
int main(int argc, char *argv[])
{
srand(time(NULL));
Item* root = constructList(20);
Item* iterator = root;
while(iterator != NULL){
     printf("%d ", iterator->value);
     iterator = iterator->next;
}
printf("\n");
shuffle(root, 20);
iterator = root;
while(iterator != NULL){
     printf("%d ", iterator->value);
     iterator = iterator->next;
}
system("PAUSE");
return EXIT_SUCCESS;
}