第八周作业



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