Python 判断两个单链表的交点

hresh 429 0

Python 判断两个单链表的交点

前言

在前面两章有介绍过单链表的基本操作以及有环链表的相关问题。本章主要分析两个单链表的交点问题。

首先声明,两个单链表只能存在 Y 型交叉,不会存在 X 型交叉。因为如果是 X 型交叉,节点在交叉点之后便不知道 next 指针指向为哪一个节点。

实战分析

判断单链表是否相交存在三种情况:

  1. 两个单链表都没有环。
  2. 两个单链表中 一个有环,一个没有环。
  3. 两个链表都有环。

情况 1

对于仅判断相交不相交的话:判断最后一个节点是否相同的办法并不慢,如果两个链表长度m,n 那么复杂度O(m+n),这是最优的复杂度。

def judge_list_equals(a:SingleLinkList, b:SingleLinkList):
    '''
    判断两个单链表是否相交,复杂度为两个链表长度之和
    :param a: 单链表a
    :param b: 单链表b
    :return:
    '''
    p = a.get_header()
    q = b.get_header()

    while p != None :
        p = p.next

    while q != None:
        q = q.next

    if p == q:
        return True
    return False

寻找交叉点。遍历两个表分别知道两个表的长度 a, b。然后让长表先走|a-b|步后,短表再开始走,直到相同,即为交叉点。(注明:本章求解的交叉点均为第一个相交点,第一个相交点是以相对单链表的开头来说,顺序行走后的某个节点)

def get_intersection(a:SingleLinkList, b:SingleLinkList):
    '''
    计算两个单链表的交叉点
    :param a:
    :param b:
    :return:
    '''
    a_size = a.size()
    b_size = b.size()

    s_max_link = a if a_size >= b_size else b
    s_min_link = a if a_size < b_size else b

    size_diff = abs(a_size-b_size)

    p = s_max_link.get_header()
    for i in range(size_diff):
        p = p.next

    q = s_min_link.get_header()

    print(p,q)

    while p != None and q != None:
        p = p.next
        q = q.next
        if p == q:
            return p
    return None

需要更新 Node 对象。

class Node():
    def __init__(self, val=None):
        self.val = val  #节点数据值
        self.next = None    #相连的下一个节点对象

    def __str__(self):
        return str(self.val)

    def __eq__(self, other):
        if other == None:
            return False
        return self.val == other.val

情况 2

当一个链表有环,另一个链表无环,那么两个链表肯定不相交。

链表相交

如上图所示,假设链表 La 有环,Lb 无环,交点在 La 环点之前。那么问题来了,Lb 的尾节点应该在哪里,不管是在 La 的入环点之前还是 La 的环上,都是有问题的。正如链表的设计理念一样,每个节点只能有一个指向下个节点的指针,Lb 的尾节点指向 None,但是 La 在 Lb 尾节点处还要指向下一个非 None 节点,而这种情况又不存在,所以情况 2 判断链表是不会相交的。

情况 3

当两个链表都为有环链表时,关于链表的交点的位置存在以下三种可能。
交点

a.交点位于两个链表入环点之前

链表相交

b.交点位于两个链表入环点之上

链表相交

c.交点位于某个链表入环点且在另一个链表的环上

关于有环链表求解入环点,在上一章中详细讲解过。

其实 a 情况和 b 情况又类似,因为它们相交之后,后面的节点都是一样的,所以还是可以采用情况 1 中的解析方法。

def get_intersection(a:SingleLinkList, b:SingleLinkList, a_size:int, b_size:int):
    '''
    计算两个单链表的交叉点
    :param a:
    :param b:
    :return:
    '''
    # a_size = a.size()
    # b_size = b.size()

    s_max_link = a if a_size >= b_size else b
    s_min_link = a if a_size < b_size else b

    size_diff = abs(a_size-b_size)

    p = s_max_link.get_header()
    for i in range(size_diff):
        p = p.next

    q = s_min_link.get_header()

    while p != None and q != None:
        p = p.next
        q = q.next
        if p == q:
            return p
    return None

if __name__ == '__main__':
    sa = SingleLinkList()
    sb = SingleLinkList()

    sa.add('a1')
    sa.add('a2')
    sa.add('c1')
    sa.add('c2')
    sa.add('c3')
    sa.add('c4')

    sb.add('b1')
    sb.add('b2')
    sb.add('b3')
    sb.add('c1')
    sb.add('c2')
    sb.add('c3')
    sb.add('c4')

    a_size = sa.size()
    b_size = sb.size()
    sa.setCycleList(3)
    sb.setCycleList(4)

    print(get_intersection(sa,sb,a_size,b_size))

首先将单链表转换为有环链表,记录转换前的链表长度,用于后续使用。

c 情况与前面两种情况不一样,交点之后的节点走的顺序队列是不同的,这就导致存在两个交点,如图所示:

链表相交

在 a3 节点处相交后,节点走序为:c2-c3-c4-c5-a3-c2.......;在 c2 节点处相交后,节点走序为:c3-c4-c5-a3-c2-c3......

两个链表的环上的节点序列是一致的,只是各自的入环点不一致,关于交点可以这么理解:相对于 La(入环点为 a3)来说它和 Lb 的交叉点即为自身的入环点,而对于 Lb(入口点为 c2)来说它与 La 的交叉点为 c2。因此,当两个有环链表相交时,存在两个交叉点,分别为各自的入环点(关于有环链表的入环点求解可以借鉴上一章的讲解内容)。

同时声明,c 情况是根据自己的理解进行分析的,如果有错误之处,还望指出,我会尽快改正。

发表评论 取消回复
表情 图片 链接 代码

分享