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

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

admin2020-06-17  33
问题 设线性表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
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)