题目

解题

可以用散列表来做，但是最好的空间复杂度也是 $O(min(A,B))$, A, B 分别是两个链表的节点个数。

解题一：散列表

// javascript
var getIntersectionNode = function(headA, headB) {
    let nodeSet = new Set();
    while (headA !== null) {
        nodeSet.add(headA);
        headA = headA.next;
    }
    while (headB !== null) {
        if (nodeSet.has(headB)) {
        	return headB;
        }
        headB = headB.next;
    }
    return null;
};

解题二

请注意观察，两个相交的链表总是拥有一个共同的尾节点。 因此，只需遍历两个链表并比较两个链表的最后一个节点即可。

上面这句话是解题的精髓！因为链表节点只能指向唯一的下一个节点，一旦相交，必有一个共同的尾节点！！

// javascript
function ResVal(tail, len) {
    this.tail = tail;
    this.len = len;
};

const getLength = (head) => {
    let length = 0;
    let tail = head;
    while (head !== null) {
        length++;
        tail = head;
        head = head.next;
    }
    return new ResVal(tail, length);
};

const getKthNode = (head, num) => {
    while (head !== null && num > 0) {
        num--;
        head = head.next;
    }
    return head;
};

const findIntersection = (l1, l2) => {
    while (l1 !== null && l2 !== null) {
        if (l1 === l2) {
            return l1;
        }
        l1 = l1.next;
        l2 = l2.next;
    }
    return null;
};
var getIntersectionNode = function(headA, headB) {
	// 遍历每个链表以获得链表的长度与尾节点
    let resA = getLength(headA);
    let resB = getLength(headB);
    // 比较尾节点 (按节点的引用比较，而不是按节点值进行比较)
    // 如果尾节点不同，立刻返回两个链表无交点
    if (resA.tail !== resB.tail) return null;
    // 将较长链表的指针向前移动，移动的步数为两个链表长度的差值
    if (resA.len > resB.len) headA = getKthNode(headA, resA.len - resB.len);
    if (resA.len < resB.len) headB = getKthNode(headB, resB.len - resA.len);
    // 同时遍历两个链表，直到两个指针指向的节点相同
    return findIntersection(headA, headB);   
};

该算法的运行时间为 $O(A+B)$，其中 A 和 B 是两个链表的长度。该算法额外占用$O(1)$的空间。