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

关注
发布于: 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型相交是一样的了。因此可以先在其中一个链表上使用环算法得到环入口，然后再从该链表开头使用上述方法三，如果在到达环入口之前找到了相交点，则返回相交点，否则说明是环内相交。
﻿
环内相交的情况，只要返回任意一个链表的环入口节点即可。
﻿
发布于: 2020 年 07 月 30 日阅读数: 61
TH

关注
还未添加个人签名 2018.02.13 加入
还未添加个人简介
发布
暂无评论
创作场景

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

方法一

方法二

方法三

方法四

TH

评论

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