8week

用户头像
一叶知秋
关注
发布于: 2020 年 07 月 26 日

有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。



1.解法一:从头开始遍历第一个链表,遍历第一个链表的每个节点时,同时从头到尾遍历第二个链表,看是否有相同的节点,第一次找到相同的节点即第一个交点。时间复杂度为O(n^2)。



2.遍历两个链表记录两个链表的长度,设较长的链表长度为len1,短的链表长度为len2,则先让较长的链表向后偏移(len1-len2)个长度。然后开始从当前位置同时遍历两个链表,当遍历到的链表的节点相同时,则这个节点就是第一个相交的节点。时间复杂度为O(len1+len2)

typedef struct node_link
{
int data;
struct node_t *next;
}Node;

node* NodeSearch(Node *head1, Node *head2)
{
if(head1==NULL || head2==NULL)
{
return NULL;
}
Node *p1=head1;
Node *p2=head2;
int len1 = 0, len2 =0;
int offset = 0;
while(p1->next!=NULL)
{
p1 = p1->next;
len1++;
}
while(p2->next!=NULL)
{
p2 = p2->next;
len2++;
}
if(p1 != p2) //如果最后一个节点不相同,返回NULL
{
return NULL;
}
offset = abs(len1 - len2);
if(len1 > len2)
{
p1 = head1;
p2 = head2;
}
else
{
p1 = head2;
p2 = head1;
}
for(int i=0; i<offset; i++)
{
p1 = p1->next;
}
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}



用户头像

一叶知秋

关注

还未添加个人签名 2018.05.13 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
作业请加“极客大学架构师训练营”标签,便于分类
2020 年 07 月 27 日 17:07
回复
没有更多了
8week