设线性表L=(a1,a2,a3,…,an-2,an-1,an)采用带头结点的单链表保存,链表中结点定义如下: 请设计一个空间复杂度为O(1)且时间上尽可能高效的算法,重新排列L中的各结点,得到线性表L’=(a1,an,a2,an-1,a3,an-2,…)

admin2020-06-17  38

问题 设线性表L=(a1,a2,a3,…,an-2,an-1,an)采用带头结点的单链表保存,链表中结点定义如下:

请设计一个空间复杂度为O(1)且时间上尽可能高效的算法,重新排列L中的各结点,得到线性表L’=(a1,an,a2,an-1,a3,an-2,…)。要求:
说明你所设计的算法的时间复杂度。

选项

答案第1步找中间结点的时间复杂度为O(n),第2步逆置的时间复杂度为O(n),第3步合并链表的时间复杂度为O(n),所以该算法的时间复杂度为O(n)。

解析
转载请注明原文地址:https://kaotiyun.com/show/jU3i777K
0

最新回复(0)