【LeetCode】每日一题：相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

解题思路

跑两遍，两遍长度加起来一样。用flag记录是否跑完了两遍，即每个flag只应该经历一次None

AC代码

# 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]:
        aflag, bflag = headA, headB
        flag = 0
        while aflag != bflag:
            if aflag.next:
                aflag = aflag.next
            else:
                if flag == 1:
                    flag = 2
                    break
                aflag = headB
                flag = 1
            bflag = bflag.next if bflag.next else headA
        return aflag if flag != 2 else None