剑指offer 52.两个链表的第一个公共节点

输入两个链表找出它们第一个公共节点，没有返回null了

解答

• 类似标记法

/**
 * 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()
    while(headA) {
        map.set(headA, true)
        headA = headA.next
    }
    while(headB) {
        if(map.get(headB)){
            return headB
        }
        headB = headB.next
    }
    return null
};

• 双指针法
• 同步遍历 A、B 链表 pA 、 pB ，直到遍历完其中一个链表（短链表），如上图，设A为长链表
• 那么此时 A、B 两遍表的长度差就为 pA 到链尾的长度，此时可以把 pB 指向长链表的表头 headA ，继续同步遍历，直到遍历完长链表
• 此时，headA 到 pB 的长度就为两链表的长度差，pB 到链表的长度与 headB 到链尾的长度一致
• 此时，可将 pA 指向 headB ，然后同步遍历 pB 及 pA ，直到有相交节点，返回相交节点，否则返回 null

var getIntersectionNode = function(headA, headB) {
    // 清除高度差
    let pA = headA, pB = headB
    while(pA || pB) {
        if(pA === pB) return pA
        pA = pA === null ? headB : pA.next
        pB = pB === null ? headA : pB.next
    }
    return null
};