问答题 设有两个链表,ha为单向链表,hb为单向循环链表。编写算法,将两个链表合并成一个单向链表,要求算法所需时间与链表长度无关。【南京航空航天大学1997四(8分)】
【正确答案】正确答案:将单向链表ha和单向循环链表hb合并成一个单向链表,要求算法所需时间与链表长度无关,只有使用带尾指针的循环单链表,这样最容易找到链表的首、尾结点,将该结点序列插入单向链表第一元素之前即可。其核心算法片段如下(设两链表均有头结点): q=hb一>next; //hb是单向循环链表的尾指针,q指向头结点 hb一>next=ha.>next; //将循环单链表最后元素结点接在ha第一元素前 ha一>next=q一>next; //将指向原单链表第一元素的指针指向循环单链表第一结点free(q); //释放循环链表头结点,ha是合并后单链表的指针 循环单链表L1和L2数据结点个数分别为m和n,将二者合成一个循环单链表时,需要将一个循环链表的结点(从第一元素结点到最后一个结点)插入另一循环链表的第一元素结点前即可。题目要求“用最快速度将两表合并”,因此应找结点个数少的链表查其尾结点。
【答案解析】