$(3$ points$)$ A randomized linked list sorting algorithm works as follows. We want to build a linked list in which the keys are in increasing order. That is$,$ every node has a smaller key than its successor in the list. For ease of discussion we assume that the keys are distinct integers from $1$ to $n.$ The algorithm randomly picks a key from the remaining keys, and inserts it into the list. This process repeats until all keys are inserted. The inserted key $k$ will skip those at the beginning of the list that are smaller than it$,$ and will stop at the first key $p$ that are greater than it$.$ We then insert the key $k$ before $p.$ To ensure that all keys will stop we assume that initially the list has only one key, $n+1.$ After we insert all keys y$/$e will have a sorted linked list from $1$ to $n+1.$

Every inserted key will stop exactly once.

The smallest key $1$ will not skip any keys.

The largest key $n$ will always skip $n-1$ keys.