title: Algorithm for Shuffling a Linked List in n log n time
body: <p>I'm trying to shuffle a linked list using a divide-and-conquer algorithm that randomly shuffles a linked list in linearithmic (n log n) time and logarithmic (log n) extra space.</p>
  
  <p>I'm aware that I can do a Knuth shuffle similar to that could be used in a simple array of values, but I'm not sure how I would do this with divide-and-conquer.  What I mean is, what am I actually dividing?  Do I just divide to each individual node in the list and then randomly assemble the list back together using some random value?</p>
  
  <p>Or do I give each node a random number and then do a mergesort on the nodes based on the random numbers?</p>