架构师训练营第 1 期 -- 第八周作业

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

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



思路：用M, N表示两个链表。如果想判断是否合并，可以用M的尾，连上N的头，用一个指针从N的头开始向后遍历，如果能更再次遍历到N的头，说明是有合并的，否则，如果遍历到next == null，则是没有合并的。

伪代码：

指针 pointer = N.tail;
while((pointer = pointer.next) != null) {
	if (pointer == N.header) {
  	return true;
  }
}
return false;

要找到合并元素，最笨的办法，如上用M的尾，连上N的头后，一个点一个点的看，是不是合并的元素。

 pointer = M.header;
while(pointer != null) {
	nPointer = N.heaer;
  while((nPointer = nPointer.next) != N.header) {
  	if (nPointer == pointer) {
    	return pointer;
    }
  }
  pointer = pointer.next;
}

时间复杂度上，为O(n^2).