Shuffling a List

Problem: Given a singly linked list, rearrange it so that every possibility has an equal chance of occurring (assuming access to a perfect random number generator)

Goal: $O(n\log n)$ time and $O(\log n)$ space

Approach with Divide and Conquer

Subproblem: Given two shuffled linked lists, create a combined shuffled linked list

Solution: Choose first element from $A$ with probability $n_1/(n_1+n_2)$. Choose first element with $B$ with probability $n_2/(n_1+n_2)$. Repeat.