两个单向链表是否存在合并元素

用户头像
周冬辉
关注
发布于: 2020 年 07 月 26 日

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

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



用(伪)代码描述算法:

步骤1:根据链接长度,调整两链表使其对齐,找到开始对比的节点

步骤2:开始对比的节点开始对比查找第一个相同的元素,记下将第一个相同的元素的位置。

步骤3:再基于往下确认两链表的元素是否相同,相同就往下对比,如果不相同,将第一个相同的元素的位置设置为空,开始对比的节点调整为这个节点的下一个节点,再跳到2步骤,直到遍历结束。

步骤4、最后根据第一个相同的元素的位置设置来判断是否有合并元素



代码:

Struct ListNodeMerge

{

ListNode* x1;

ListNode* x2;

}

 //ListNodeMerge* merge 合并的开始节点

bool FindMergeList(ListNode* headm , int m, ListNode* headn, int n, ListNodeMerge* merge)

{

ListNode* noden, nodem, noden_x, nodem_x, noden_x_pre, nodem_x_pre;

 

noden= headn;

nodem= headm;

noden_x_pre=nodem_x_pre=nodem_x =noden_x=NULL;

//调整两链表使其对齐

 if(m>n)

{

for( int i=0; i<m-n;i++)

nodem = nodem ->next;

}

else

{

for( int i=0; i<n-m;i++)

noden = noden ->next;

}

 

while (noden)

{

 

//查找第一个相同的元素

while(noden->data != nodem->data)

{

noden_x_pre= noden;

nodem_x_pre= nodem;

noden = noden ->next; nodem = nodem ->next;

}

 

//标记合并的元素

noden_x= noden;

nodem_x = nodem;

 

//后续项目的元素是否相同

while(noden->data == nodem->data)

{         

noden = noden ->next; nodem = nodem ->next;

}

}

 

if(noden_x)

{

nodem_x_pre->next = noden_x;

merge-> x1= noden_x;

merge-> x2= nodem_x;

 

//TODO根据条件是否删除多余的重复节点

//删除从nodem_x开始的节点

ListNode* tmp;

while(nodem_x)

{

tmp =nodem_x;

nodem_x= nodem_x->next;

delete tmp;

}

return true;

}

return false;

}



元素合并仅仅将两个链接都遍历一遍,时间复杂度O(max(m,n))即O(n)

空间复杂度为O(1)



用户头像

周冬辉

关注

还未添加个人签名 2020.04.14 加入

还未添加个人简介

评论

发布
暂无评论
两个单向链表是否存在合并元素