架构师训练营第八周作业

有两个单向链表（链表长度分别为 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

本文由 biezhi 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2020/07/30 10:50