求star

题目:tada:#

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

解题:cherries:#

①使用Set类#

TIP

​ 先将链表A存入一个Set集合，然后遍历链表B，第一个重复的就是相交的起始节点,时间复杂度O(m+n)

/**
 * 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) {
    const s= new Set()
    while(headA){
        s.add(headA)
        headA = headA.next
    }
    while(headB){
        if(s.has(headB)){
            return headB
        }
        headB = headB.next
    }
    
};

②双指针#

TIP

​ 定义两个指针pA,pB，分别遍历链表A和链表B，一个遍历完了就遍历另一个，由于两个指针走过的路程是一样的(同时开始),那么当第一次pA===pB的时候，就是相交的起点

/**
 * 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) {
    if(headA==null || headB == null){
        return null
    }
    let pA= headA,pB = headB
    while(pA !== pB){
      pA = pA === null ? headB : pA.next
      pB = pB === null ? headA : pB.next
    }
    return pA
};