Shuffling a linked list

https://www.cnblogs.com/evasean/p/7232572.html

Shuffling a linked list. Given a singly-linked list containing n items, rearrange the items uniformly at random. Your algorithm should consume a logarithmic (or constant) amount of extra memory and run in time proportional to nlogn in the worst case.

此题要求对单向链表进行随机排序，可以考虑先实现个链表的归并排序(见我的另一篇文章)，再改造成这里的随机排序。

 70     private Node sort(Node head){
 71         if(head == null || head.next == null) return head;
 72         Node slow = head;
 73         Node fast = head;
 74         //取中间节点
 75         while(fast.next != null && fast.next.next != null){
 76             slow = slow.next;
 77             fast = fast.next.next;
 78         }
 79         Node left = head;
 80         Node right = slow.next;
 81         slow.next = null; //将左右链表分开
 82         left = sort(left);
 83         right = sort(right);
 84         return merge(left,right);
 85     }
 86     private Node merge(Node left, Node right){
 87         //System.out.println("left="+left.element+",right="+right.element);
 88         Node aux = new Node(); //需要耗费logn的额外空间
 89         Node l= left;
 90         Node r = right;
 91         Node current = aux;
 92         while(l != null && r!=null){
 93             int rand = StdRandom.uniform(2);
 94             if(rand == 0){ //如果随机数选为0，则从左侧选取元素
 95                 current.next = l;
 96                 current = current.next;
 97                 l= l.next;
 98             }else{ //如果随机数选为1，则从右侧选取元素
 99                 current.next = r;
100                 current = current.next;
101                 r = r.next;
102             }
103         }
104         if(l!=null) current.next = l; // 如果左侧没遍历完，将其连接至current后
105         else if(r != null) current.next = r; //如果右侧没遍历完，将其连接至current后
106         return aux.next; //返回归并好的链表
107     }

https://web.stanford.edu/class/cs9/sample_probs/ListShuffling.pdf