数据结构算法题,合并两个链表的算法,计算时间复杂度。

2024-12-03 19:09:28
推荐回答(2个)
回答1:

如果要比较两个链表的大小,那就得将两具链表分别访问一次,这样至少需要m+n次访问,不如直接访问一个链表到结束,然后将另一个链表连接到结尾处,这样平均需要访问(m+n)/2次,这样算法的时间复杂度应该为O(m+n)

回答2:

简单,比较m和n的大小,选择小的那个链表,找到它的尾节点,然后把另一个链表的头连接到这个链表的尾,最后把hc赋值为当前链表的头,返回即可。
时间复杂度是min(m,n)+c,c是常数。