链表

两个链表的交点

• 两个链表相交，则相交点之后的节点都是相同的
• A 走完走 B，B 走完走 A，步数一样就会相遇。
• 举例：

A 长度 = 3 (a1 → a2 → c1 → c2 → c3)
B 长度 = 4 (b1 → b2 → b3 → c1 → c2 → c3)
pA: a1 → a2 → c1 → c2 → c3 → null → b1 → b2 → b3 → c1 ←★
pB: b1 → b2 → b3 → c1 → c2 → c3 → null → a1 → a2 → c1 ←★
最后pA和pB都走了9步，在c1相遇, 因为c1是相交点

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode p1 = headA;
    ListNode p2 = headB;
    while (p1 != p2) {
        p1 = p1 == null ? headB : p1.next; // 如果p1走到头，则从headB开始
        p2 = p2 == null ? headA : p2.next; // 如果p2走到头，则从headA开始
    }
    return p1;
}