给定两个单向链表(长度分别为M,N),链表的尾部有部分重合(长度为S),找到重合的部分,输出重合的部分,和重合部分在两个链表中的位置。

算法思路：

1. 计算两个链表的长度差diff；

2. 长链表先移动diff个节点，然后和短链表一起向后遍历，直到找到第一个相同的节点；

3. 如果两个链表没有重合部分，则返回null；

4. 如果有重合部分，则返回重合部分的起始节点和两个链表中的位置。

代码实现：

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

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    # 计算两个链表的长度
    lenA, lenB = 0, 0
    pA, pB = headA, headB
    while pA:
        lenA += 1
        pA = pA.next
    while pB:
        lenB += 1
        pB = pB.next

    # 长度差
    diff = abs(lenA - lenB)
    # 长链表先移动diff个节点
    pA, pB = headA, headB
    if lenA > lenB:
        for i in range(diff):
            pA = pA.next
    else:
        for i in range(diff):
            pB = pB.next

    # 一起向后遍历，找到第一个相同的节点
    while pA and pB and pA != pB:
        pA = pA.next
        pB = pB.next

    if pA == pB:
        return pA
    else:
        return None

时间复杂度：$O(m+n)$，其中m和n分别是两个链表的长度。