架构师训练营第 8 周作业 算法与数据结构

用户头像
TH
关注
发布于: 2020 年 07 月 30 日

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





方法一

最简单的方法就是在遍历其中一个链表,并在遍历其每个节点的时候遍历一遍另一个链表,判断该节点是否在另一个链表中。这个算法的时间复杂度为O(mn),空间复杂度为O(1),虽然简单但时间复杂度最高。

def find_intersection(chain_a, chain_b):
node_a = chain_a.start
node_b = chain_b.start
if node_a == node_b:
print 'intersect at', node_a
return
while node_a.next:
while node_b.next:
if node_a == node_b:
print 'intersect at', node_a
return
print 'no intersection'



方法二

由于单链表的每个节点只有一个next,因此相交后所有节点必然都重合,可以分别将两个链表压入两个栈,如果压完后两个栈顶不同,则说明两个链表没有相交,如果相同,则同时出栈,直到两个栈顶不同,那么上一个出栈的节点就是相交点。该算法的时间复杂度是O(n)(假设n大于m),空间复杂度为O(m+n)。

def find_intersection(chain_a, chain_b):
node_a = chain_a.start
node_b = chain_b.start
if node_a == node_b:
print 'intersect at', node_a
return
stack_a = Stack()
stack_b = Stack()
stack_a.put(node_a)
stack_b.put(node_b)
while node_a.next:
node_a = node_a.next
stack_a.put(node_a)
while node_b.next:
node_b = node_b.next
stack_b.put(node_b)
last = None
while True:
if stack_a.is_empty() or stack_b.is_empty():
break
node_a = stack_a.pop()
node_b = stack_b.pop()
if node_a == node_b:
last = node_a
continue
if node_a != node_b:
break
if last:
print 'intersect at', last
else:
print 'no intersection'



方法三

如果两个链表长度相同,那么同时开始遍历,在相交处一定会相遇,如果两个链表长度不同,则只要让长的先走几步,走到两个链表剩余长度相同,那么就可以开始同时遍历。该算法时间复杂度O(n)(假设n大于m),空间复杂度O(1)。这个算法的前提是已知两个链表的长度。

def find_intersection(chain_a, chain_b):
node_a = chain_a.start
node_b = chain_b.start
if node_a == node_b:
print 'intersect at', node_a
return
if len(chain_a) >= len(chain_b):
step = len(chain_a) - len(chain_b)
for i in range(step):
node_a = node_a.next
else:
step = len(chain_b) - len(chain_a)
for i in range(step):
node_b = node.next
while node_a.next:
if node_a.next == node_b.next:
print 'intersect at', node_a.next
return
node_a = node_a.next
node_b = node_b.next
print 'no intersection'



方法四

由于链表中每个节点的地址是确定且唯一的,因此可以对其中一个链表中每个节点的地址计算哈希值,存入哈希表,然后再对另一个链表中的每个节点的地址依次计算哈希值,只要这个值已经在哈希表里,则说明当前节点就是相交点。该算法时间复杂度为O(m+n),空间复杂度为O(n)(假设n大于m)。

def find_intersection(chain_a, chain_b):
node_a = chain_a.start
node_b = chain_b.start
if node_a == node_b:
print 'intersect at', node_a
return
hash_table = {}
while node_a.next:
hash_table[hash(node_a.addr)] = node_a
node_a = node_a.next
while node_b.next:
if hash_table[hash(node_b.addr)]:
print 'intersect at', node_b
return
node_b = node_b.next
print 'no intersection'



上述四种算法都只适用于链表无环的情况,下面分析一下链表有环的情况。



如果链表有环,则环一定是两个链表共用的,因此使用判断链表是否有环的算法,如果得出的结果是只有一个链表有环,那么两个链表一定不相交。如果两个链表都有环,那么相交点有两种情况:在环外相交和在环内相交。



在环外相交的情况,由于环是共用的,因此不看环的话就跟上面所讲的Y型相交是一样的了。因此可以先在其中一个链表上使用环算法得到环入口,然后再从该链表开头使用上述方法三,如果在到达环入口之前找到了相交点,则返回相交点,否则说明是环内相交。



环内相交的情况,只要返回任意一个链表的环入口节点即可。



用户头像

TH

关注

还未添加个人签名 2018.02.13 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第8周作业 算法与数据结构