单链表的实现

插入

1665218795671

后向遍历


xxxxxxxxxx
4
1
while (p != NULL) {
2
    // 某些处理
3
    p = p->next;
4
}

链表只能按顺序一个个找，所以

求表长的时间复杂度为 O(n)

查找某个结点的时间复杂度为 O(n)

答案与解析：

答案： D
解析：
如果先建立链表，然后依次插入建立有序表，每次插入都需要遍历一次链表寻找插入位置，时间复杂度为O(n²)。
如果先对数组排序，再建立链表，建立链表的时间复杂度为O(n)，数组排序的最好时间复杂度为O(n log₂n)，总时间复杂度为O(n log₂n)。