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

题目：有两个单向链表(链表长度分别为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)