I have come across this video on skip lists:
Clearly, the creation of skip-list from a sorted singly linked list is a randomized algorithm. But I am confused: is it a Las Vegas algorithm or a Monte Carlo algorithm?
I feel it is a Monte Carlo algorithm since there is a possiblity of an incorrect output(degenerate case where every node is in every level), and if we don't maintain a checking condition, we won't know where the algo went wrong.
Am I correct?
P.S. My first question here.