题目内容
(请给出正确答案)
[主观题]
设ha和hb分别是两个带附加头结点的非递减有序单链表的表头指针,试设计一个算法,将这两个有序
链表合并成一个非递增有序的单链表,要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间,表中允许有重复的数据。
查看答案
如果结果不匹配,请 联系老师 获取答案
算法实现的思路为:在有序单链表中插入一个数据元素x,首先要找到该元素应该插入到什么位置,才能保证插入后的单链表仍为有序表。因此,算法的第一步是寻找x的位置:设置指针p、q,最初p指向头结点,q指向头结点的下一个结点,比较q所指数据域的值与x的大小,如果小于x,则p、q分别向后移动一个位置,使p始终作为q的前驱结点,然后重复上面的比较过程;如果比较结果大于x或是比较到最后单链表结束了,则找到了插入位置,在p与q之间插入结点x即可。算法的具体实现如下:
设链表不带头结点,且所有操作均在表头进行,则下列最不适合作为链栈的链表是()。
A.只有表头结点指针,没有表尾指针的双向循环链表
B.只有表尾结点指针,没有表头指针的双向循环链表
C.只有表头结点指针,没有表尾指针的单向循环链表
D.只有表尾结点指针,没有表头指针的单向循环链表
在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是(53)。
A.O(1)
B.O(n)
C.O(nlogn)
D.O(n2)