单链表有序插入结点的时间复杂度分析

假设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为 O(n)。

分析:

为了保持链表有序，需要找到新结点应该插入的位置。最坏情况下，新结点需要插入到链表的末尾，这就需要遍历整个链表才能找到插入位置。因此，时间复杂度为 O(n)。

原文地址: https://www.cveoy.top/t/topic/qcop 著作权归作者所有。请勿转载和采集!