题解 | 链表相交

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

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    # 在这里补充代码
    pa = headA
    pb = headB
    if not pa or not pb:#若pa，pb为空，则一定没有相交节点
        return None
    while pa!=pb: #循环结束，pA和pB指向相同的节点或者pA和pB都为null
        if pa == None:
            pa = headB
        if pb == None:
            pb = headA
        # 原理当listA和listB相交时，设listA的不相交长度为a，listB的不相交长度为b，listA和listB的相交节点到链表尾部的距离为c
        # 则pA走过距离为a+c+b，pB走过距离为b+c+a，走过相同长度的距离后到达相交点，返回即可

        # 若listA和listB不相交，则pA和pB始终不等，最后不仅pA走过ListA+ListB的长度,指向null，pB也指向null及无相交节点    
        pa=pa.next
        pb=pb.next
        
    return pa














# 你不需要关心主函数内容！
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()