Question

建立一个有n个元素的有序单链表的时间复杂度度为什么是O(n^2) 呢？

Answer 1

因为o(n^2) ,对单链表而言，一些快速的排序算法，不能用，只能用直接插入等o(n^2) 级的排序算法来实现排序。因为是有序单链表那么每次插入到链表尾结点，那么每次插入都要从头扫到尾，然后1+2+3+... m = O(m^2)这样。

有序链表就是，从头结点开始到链表结尾，节点中数据有序排列，比如说递增，递减或者其他满足一定条件的规则。单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；

列表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向nuLL的指针。