架构师训练营第八周作业

/ 架构师训练营 / 没有评论 / 377浏览

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

  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