链表合并问题

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

请用代码（或伪代码）描述算法，并给出时间复杂度。





算法思路 - 同时遍历两个链表。设右边为current1(对应第一条链表),current2(对应第二条链表)。当current1到尽头后，使current1遍历第二条链表。同样当current2到尽头后：使其遍历第一条链表。

在第二次遍历时：current1==current2：此时是merge point。否则没有merge point。



代码样例如下：

int findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {

SinglyLinkedListNode* current1=head1,SinglyLinkedListNode* head2 = head2;

while(current1 !=current2){

if(current1->next ==nullptr)

current1=head2;

else

current1=current1->next;

if (current2->next == nullptr)

current2 = head1;

else

current2 = current2->next;

}

return current1->data;

}



时间复杂度：O(n^2）

空间复杂度：同时存储2个参数 - O(2)