Question

一道数据结构题

已知两个递增有序的单链表（长度分别为m和n），如果将其归并成一个按元素递增的有序的单链表，可能达到的最优时间复杂度为多少？

谢谢

Answer 1

首先每次插入都要比较，那么最好的情况就是其中一个单链表的第一个元素值比另一个单链表的最后一个元素都大，那么也就是比较m或n次，这取决于m和n哪个大并且用那个作为元素少的单链表作为被比较的，所以最优时间复杂度为O(m)或O(n)

Answer 2

我的发帖人

追问

？