架构师训练营第八周作业

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。

1. 计算链表1、2的长度m，n，取得长的链表(比如链表2)

2. 链表2头指针后移n-m，使得两个链表同长

3. 遍历第二步产生的两个链表，若节点一样，则返回该节点

4. 若返回null，则链表没有合并，否则为合并后的节点，时间复杂度为O(m+2n)，空间复杂度O(1)

function findMergeNode(link1, link2) 
	result <- null
	m <- link1.length
	n <- link2.length
	differ <- m > n ? m - n : m -n
	[shortLink, longList] <- m > n ? [link1, lnk2] : [link2, link1]
	while differ-- > 0 do
	 longLink <- longLink.next
	end while
	while longLink do
	 if longLink == shortLink then
	   result <- longList
	 else
	   longLink <- longLink.next
	   shortLink <- shortLink.next
	 end if
	end while
end function