问题标题:
数据结构算法题,合并两个链表的算法,计算时间复杂度。已知指针ha和hb分别指向两个单链表的头结点,并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起(即令其
问题描述:
数据结构算法题,合并两个链表的算法,计算时间复杂度。
已知指针ha和hb分别指向两个单链表的头结点,并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起(即令其中一个表的首结点连在另一个表的最后一个结点之后),假设指针hc指向连接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。
韩艳回答:
简单,比较m和n的大小,选择小的那个链表,找到它的尾节点,然后把另一个链表的头连接到这个链表的尾,最后把hc赋值为当前链表的头,返回即可。
时间复杂度是min(m,n)+c,c是常数。
点击显示
其它推荐
热门其它推荐