面试题 02.07. 链表相交 python_相交链表 python

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        curA = headA
        curB = headB
        sizeA = 0
        sizeB = 0
        while curA != None:
            sizeA += 1
            curA = curA.next
        while curB != None:
            sizeB += 1
            curB = curB.next
        
        curA = headA
        curB = headB
        if sizeA > sizeB:
            n = sizeA - sizeB
            while n:
                curA = curA.next
                n -= 1
        elif sizeA < sizeB:
            n = sizeB - sizeA
            while n:
                curB = curB.next
                n -= 1
        
        # while curA.val != curB.val and curA != None:
        # ❗注意是节点的相同而不是值的相同。因此不需要取val属性。否则：
        # 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5],
        #  skipA = 2, skipB = 3
        # while里取val则输出：Intersected at '1'.正确输出：Intersected at '8'
        while curA != curB and curA != None:
            curA = curA.next
            curB = curB.next
        return curA