It can be inserted anywhere. Note that if you insert it in the beginning the TC will be O(#s +c), but it is also O(#s+ n). Remember that the TC is an Upper Bound. Make the program as fast as possible, provided it follows the specification. So in this case insert it at the beginning of the ULL.
原文：http://www.cnblogs.com/miaoz/p/4470294.html