Python中如何判断两个链表是否相交

2023-04-11 00:00:00 链表相交如何判断

判断两个链表是否相交可以通过以下方法：

遍历链表1，记录链表1的长度len1，同时记录链表1的尾结点tail1。
遍历链表2，记录链表2的长度len2，同时记录链表2的尾结点tail2。
比较tail1和tail2是否相等，如果不相等，则链表1和链表2一定不相交。
如果tail1和tail2相等，则比较链表1和链表2的长度。
如果len1>len2，链表1先向后移动len1-len2个结点。
如果len2>len1，链表2先向后移动len2-len1个结点。
然后同时遍历链表1和链表2，比较每个结点是否相等。

以下是Python代码实现：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def get_intersect_node(headA, headB):
    if not headA or not headB:
        return None

    len1, tail1 = get_length_and_tail(headA)
    len2, tail2 = get_length_and_tail(headB)

    if tail1 != tail2:
        return None

    if len1 > len2:
        for i in range(len1 - len2):
            headA = headA.next
    else:
        for i in range(len2 - len1):
            headB = headB.next

    while headA and headB:
        if headA == headB:
            return headA
        headA = headA.next
        headB = headB.next

    return None

def get_length_and_tail(head):
    length = 0
    tail = None
    while head:
        length += 1
        tail = head
        head = head.next
    return length, tail

# 测试代码
a = ListNode('p')
a.next = ListNode('i')
a.next.next = ListNode('d')
a.next.next.next = ListNode('a')
a.next.next.next.next = ListNode('n')
a.next.next.next.next.next = ListNode('c')
a.next.next.next.next.next.next = ListNode('o')
a.next.next.next.next.next.next.next = ListNode('d')
a.next.next.next.next.next.next.next.next = ListNode('e')
b = ListNode('皮')
b.next = ListNode('蛋')
b.next.next = a.next.next.next.next.next
c = get_intersect_node(a, b)
if c:
    print(c.val)
else:
    print('不相交')

# 输出结果为：n

相关文章