假设单链表LA和LB分别表示两个已排序(非递减)的线性表A和B。现在要将LA和LB归并为一个新的单链表LC,表示线性表C,且C中的元素仍按非递减顺序排列。若已知A的长度为m,B的长度为n,以下关于归并过程的描述,哪一项**不准确**?
答案解析
选项A:当两个链表元素完全交错排列时,比如A的前i个元素小于B的前i个元素,那么至少要比较min(m, n)次。选项B:当LA和LB当前结点值相等时,选择哪一个添加并不会影响最终结果的正确性。选项C:归并操作仅仅是修改指针指向,没有额外的辅助空间,空间复杂度为O(1)。选项D: 即使A和B中存在大量重复元素,算法仍然需要扫描两个链表,时间复杂度为O(m+n)。此题的选项D略有歧义,容易让人觉得复杂度是否会因为重复元素而有所不同。此题为难题。
正确答案:D