"""
相交链表
"""
from typing import List, Optional


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


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        """
        思路:如果存在交点,则肯定在两个链表分别遍历对方时相交
        :param headA:
        :param headB:
        :return:
        """
        if not headA or not headB:
            return None
        nodeA, nodeB = headA, headB
        while nodeA != nodeB:
            nodeA = nodeA.next if nodeA else headB
            nodeB = nodeB.next if nodeB else headA
        return nodeA


if __name__ == '__main__':
    l1 = ListNode(4)
    l1.next = ListNode(1)
    l1.next.next = ListNode(8)
    l1.next.next.next = ListNode(4)
    l1.next.next.next.next = ListNode(5)
    # l1.next.next.next.next.next = ListNode(9)
    # l1.next.next.next.next.next.next = ListNode(9)
    l2 = ListNode(5)
    l2.next = ListNode(6)
    l2.next.next = ListNode(1)
    l2.next.next.next = ListNode(8)
    l2.next.next.next.next = ListNode(4)
    l2.next.next.next.next.next = ListNode(5)
    result = Solution().getIntersectionNode(l1, l2)
    print(result)