leetcode-相交链表

160. 相交链表

注：两个链表相交不是指两个节点的值相等，而是指节点所在的地址

# 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) -> Optional[ListNode]:
        curA = headA
        curB = headB
        lenA = 0
        lenB = 0
        # 求出两个链表的长度
        while curA:
            lenA += 1
            curA = curA.next
        while curB:
            lenB += 1
            curB = curB.next
        # 这个地方是因为上面求长度的时候已经遍历到curA和curB的末尾了
        curA = headA
        curB = headB
        if lenA > lenB:
            lenA, lenB = lenB, lenA
            curA, curB = curB, curA
        # 使curA和curB在同一起点上
        for _ in range(lenB - lenA):
            curB = curB.next
        
        while curA:
            if curA == curB:
                return curA
            else:
                curA = curA.next
                curB = curB.next
        return None