思想

双指针算法不仅应用于链表，在数组等数据结构中也有广泛应用。
核心思路是指向问题中的关键节点，根据问题的上下文逻辑变换位置，最终解决问题。

实例

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

输入：
（1）headA: ListNode，一个链表
（2）headB: ListNode，另一个链表

输出：
ListNode，如果链表中无相交节点返回 None，有则返回相交的起始节点。

输入的两个链表 A 和 B 无环

举例：
当 headA = [4,1,8,4,5], headB = [5,6,1,8,4,5]，其中 [8,4,5] 共用时，返回环相交的起始节点 8。

关键点

核心是要设计一个方案让从 headA 和 headB 开始的指针能在相交节点相遇。
两个起点的长度不同，天然的结构是无法实现的，利用无环的特性，如果让两个起点在遍历自身链表结束后从对方的起始开始遍历，这样如果两条链表有相交节点就会出现在起始节点相遇的情况，无相交时会遍历完全部节点。
（1）有相交节点

    headA ---\
              meet --- end 
headB ------ /

两个指针 pA 和 pB 分别从 headA 和 headB 开始遍历，分别走到 end 时交换彼此的开头。
当第一次 pA = pB 时，节点是 meet。
（2）无相交节点

    headA --- endA
headB ------- endB

两个指针 pA 和 pB 分别从 headA 和 headB 开始遍历，分别走到 end 时交换彼此的开头。
pA 和 pB 同时走到终点，没有过相遇，此时返回 None。

编码

from typing import Optional


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


def intersection_of_two_linked_lists(headA: ListNode, headB: ListNode) -> Optional[ListNode]:
    # 初始化
    pA = headA
    switchA = False
    pB = headB
    switchB = False
    # 遍历寻找相交起始节点
    while switchA is False or switchB is False or (pA is not None and pB is not None):
        # 任何时候 pA 等于 pB 即是起始相交节点
        if pA == pB:
            return pA
        # pA 遍历 headA 后遍历 headB
        if pA is None:
            pA = headB
            switchA = True
        else:
            pA = pA.next
        # pB 遍历 headB 后遍历 headA
        if pB is None:
            pB = headA
            switchB = True
        else:
            pB = pB.next