第八周架构师训练营作业

 关注

发布于: 2020 年 07 月 27 日

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
﻿
方法一：
遍历其中一个链表，对于上面的每一个节点，再遍历另一个链表，如果有相同，返回。伪代码如下：
pA <- Head(ListA)
while pA != null
	pB <- Head(ListB)
  while (pB != null)
  	if Node(pA) = Node(pB)
    	return Node(pA)
      pB <- Next(pB)
	pA <- Next(pA)
return null
时间复杂度为O(mn)，空间复杂度为O(1)（没有额外的空间）
﻿
方法二：
两个指针同时遍历两个链表，当一个指针到达链表末尾的时候，指针指向另一个链表头，直到有相同的节点或者都到达末尾为止。伪代码如下：
pA <- Head(ListA)
pB <- Head(ListB)
while pA != null AND pB != null
	if Node(pA) = Node(pB)
  	return Node(pA)
  pA <- Next(pA)
  pB <- Next(pB)
  if Node(pA) = null
  	pA <- Head(ListB)
  if Node(pB) = null
  	pB <- Head(ListA)
return null
   
时间复杂度为O(m+n)，空间复杂付为O(1)
﻿
方法三：
计算两个链表的长度，较长的链表先前进两个链表长度之差的步数，再两个链表同时遍历比较。伪代码如下：
p1 <- Head(ListA)
p2 <- Head(ListB)
len1 <- Length(ListA)
len2 <- Length(ListB)
delta <- len1 - len2
if len1 < len2
	delta <- len2 - len1
  p1 <- Head(ListB)
  p2 <- Head(ListA)
for delta to 0
	p1 <- Next(p1)
while p1 != null AND p2 != null
	if Node(p1) = Node(p2)
  	return Node(p1)
  p1 <- Next(p1)
  p2 <- Next(p2)
return null
时间复杂度为O(max(m,n))，空间复杂度为O(1)

发布于: 2020 年 07 月 27 日阅读数: 28

子豪sirius

 关注

还未添加个人签名 2018.05.03 加入

还未添加个人简介

评论 (1 条评论)

发布