问答题已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O(m+n+p)，其中m、n和p分别为三个表的长度。【清华大学1995一(15分)】

【正确答案】正确答案：要求留下三个链表中的公共数据，首先查找两表A和B中的公共数据，再去C中查找有无该数据。要消除重复元素，应记住前驱，要求时间复杂度为O(m+n+p)，在查找每个链表时，指针不能回溯。算法主要由while(pa&&pb&＆pc)控制。若三表有一个到尾，则结束循环。A表头结点作监视哨，否则第一个结点要特殊处理。算法最后要给新A表置结尾标记，同时若原A表没到尾，还应释放剩余结点所占的存储空间。

【答案解析】