160.相交链表

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
    // 哈希表记录节点
    let map = new Map()
    let cur = headA
    while (cur) {
        map.set(cur, true)
        cur = cur.next
    }

    cur = headB
    // map中存在的第一个节点即为相交节点
    while (cur) {
        if (map.has(cur)) {
            return cur
        }
        cur = cur.next
    }

    return null
};

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
// 内存优化，双指针
var getIntersectionNode = function (headA, headB) {
    if (!headA || !headB) {
        return null
    }
    // a走完走b，b走完走a，他们会在公共点相遇，如果没有公共点，他们最后同时为null
    let p1 = headA
    let p2 = headB
    while (p1 !== p2) {
        p1 = p1 === null ? headB : p1.next
        p2 = p2 === null ? headA : p2.next
    }
    return p1
}