问题
问答题
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。
设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为,请设计一个时间上尽可能高效的算法,找出由str1和str2所指的两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。要求:
说明你所设计算法的时间复杂度。
答案
参考答案:
时间复杂度为:O(m+n)或O(max(m,n))。其中m、n分别为两个链表的长度。