leetcode 160. 相交链表 js 实现

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

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
// 双指针  时间复杂度 O(m+n),空间复杂度 O(1)
// 核心逻辑：消除长度差
// 1. 假设相交链表长度为 c，链表A为为长链表，则 长链表长度=a+c; 链表 B 为短链表，则短链表长度=b+c
// 2. 长链表和短链表同时向前走，当短链表走到末尾的时候，此时双方各自都走过的是短链表的长度，
// 3. 此时将短链表指向长链表，接着往下走，当长链表走到末尾的时候，此时双方各自都走过长链表的长度
// 4. 短链表走过的是长链表后半段（短链表的长度）和长链表前半段（长链表长度-短链表长度）。
// 5. 此时将长链表指向短链表头部，短链表指向下一个节点（刚好与短链表指向的位置重合，即后面的长度都一致）
// 6. 这样就可以一直往下遍历，来判断当两个链表值一致即返回，null=null 也会返回。

var getIntersectionNode = function(headA, headB) {
    if(!headA || !headB){
        return null;
    }
    // 双指针
    let p1 = headA;
    let p2 = headB;
    while(p1 !== p2 ){
        p1 = p1 === null ? headB : p1.next;
        p2 = p2 === null ? headA : p2.next;
    }
    return p1
};