给定两个已排序(非递减)的单链表LA和LB,分别存储线性表A和B。现需将LA和LB归并为一个新的单链表LC,存储线性表C,且C中的元素仍按非递减顺序排列。在归并过程中,若LA和LB中存在相同值的结点,以下哪种处理方式在**最坏情况**下,其时间复杂度与其他方式**显著不同**?(假设链表长度均为n)
答案解析
选项A:当LA和LB中存在大量连续值相等的结点时,例如LA=(1,1,1,...1),LB=(1,1,1,...1),此方法需要遍历LA和LB的所有结点,并依次添加到LC末尾,时间复杂度为O(2n), 约为O(n)。选项B:跳过LB中相等节点,仍然需要遍历LA和LB的大部分节点,时间复杂度仍为O(n)。选项C:每次只保留一个相等值,避免重复添加,时间复杂度为O(n)。选项D: 将LA相等节点优先插入,然后插入LB相等节点,仍然需要遍历LA和LB的大部分节点,时间复杂度仍为O(n)。注意,这里考察的是“最坏情况”下时间复杂度“显著不同”,A,B,C,D在时间复杂度上并无本质区别(都是O(n)),但是当处理重复节点时,添加的节点数量会有差异,而选项A的处理方式会导致添加的节点数量最多,虽然最坏情况的时间复杂度并没有明显不同,但是如果比较添加的节点数量,选项A远超其他选项,此题为偏难题。
正确答案:A