Question

数据结构 求将单链表逆置的的时间复杂度 详细解释 高手来

Answer 1

其时间复杂度是O(n)，n是链表结点的个数，逆置时，其算法思想是将原表中的结点循着链依次摘下并插入到新表的表头，因此算法中while循环将执行n趟，然后根据算法我们来计算T(n)， T(n)=2+4*n+1+1。解释一下这个算式的由来，2是指while循环前的两个基本操作，4*n是while循环执行n趟，每趟循环中循环体内有3个基本操作和1次循环判断操作，接下来的两个1，前一个1表示最后一趟循环之后还需进行1次循环判断，后一个1是指return操作。因此T(n)=4n+4， 则O(T(n))=O(4n+4)=O(4n)=O(n)。

追问

完美！