问题 问答题

假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。

设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为,请设计一个时间上尽可能高效的算法,找出由str1和str2所指的两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。要求:

说明你所设计算法的时间复杂度。

答案

参考答案:

时间复杂度为:O(m+n)或O(max(m,n))。其中m、n分别为两个链表的长度。

选择题
单项选择题