题解 | 链表相交

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


def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    # 在这里补充代码
    #定义两个指针,分别指向两个链表的头指针
    pa = headA
    pb = headB
    lenA = 0
    lenB = 0
    #遍历两个链表,记录长度
    while pa != None:
        lenA += 1
        pa = pa.next
    while pb != None:
        lenB += 1
        pb = pb.next
    #重新定位指针位置
    pa = headA
    pb = headB
    #判断哪个链表的长度长
    if lenA > lenB:
        n = lenA - lenB
        for _ in range(n):
            pa = pa.next
        #遍历到两个链表距离结尾一样的长度
        while pa != None:
        #如果地址一样就返回交点
            if pa == pb:
                return pa
            pa = pa.next
            pb = pb.next
    else:
        n = lenB - lenA
        for _ in range(n):
            pb = pb.next
        while pa != None:
            if pa == pb:
                return pa
            pa = pa.next
            pb = pb.next
    return None
    pass


# 你不需要关心主函数内容！
def main():
    # 读入数据
    lenA, lenB, commonLen = map(int, input().split())

    # 读入链表A的独立部分
    valuesA = list(map(int, input().split()))
    # 读入链表B的独立部分
    valuesB = list(map(int, input().split()))
    # 读入公共部分
    valuesCommon = list(map(int, input().split()))
    nodesCommon = []
    if commonLen == 0:
        nodesCommon = []
    else:
        nodesCommon = [ListNode(x) for x in valuesCommon]

    # 构建链表
    nodesA = [ListNode(x) for x in valuesA]
    nodesB = [ListNode(x) for x in valuesB]

    # 连接链表A的独立部分
    for i in range(len(nodesA) - 1):
        nodesA[i].next = nodesA[i + 1]

    # 连接链表B的独立部分
    for i in range(len(nodesB) - 1):
        nodesB[i].next = nodesB[i + 1]

    # 连接公共部分
    for i in range(len(nodesCommon) - 1):
        nodesCommon[i].next = nodesCommon[i + 1]

    # 设置头节点并连接公共部分
    headA = None
    headB = None

    if len(nodesA) > 0:
        headA = nodesA[0]
        if len(nodesCommon) > 0:
            nodesA[-1].next = nodesCommon[0]
    elif len(nodesCommon) > 0:
        headA = nodesCommon[0]

    if len(nodesB) > 0:
        headB = nodesB[0]
        if len(nodesCommon) > 0:
            nodesB[-1].next = nodesCommon[0]
    elif len(nodesCommon) > 0:
        headB = nodesCommon[0]

    # 调用函数获取结果
    result = getIntersectionNode(headA, headB)

    # 输出结果
    if result is None:
        print("null")
    else:
        print(result.val)


if __name__ == "__main__":
    main()