单链表
作者/cherryqi　时间/2006-8-4 15:06:00　类别/数据结构 查看/
　发表评论　以论坛方式查看
标签：数据结构
 已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。

算法如下: 
LinkList Link( LinkList L1 , LinkList L2 )
{
//将两个单链表连接在一起
ListNode *p , *q ;
p=L1;
q=L2;
while ( p->next ) p=p->next; //查找终端结点
p->next = q->next ; //将L2的开始结点链接在L1之后
return L1 ;
} 
本算法的主要操作时间花费在查找L1的终端结点上，与L2的长度无关，所以本算的法时间复杂度为： 
m+1=O(m)
查看该用户更多文章>>