“ 今日继续算法相关的题目练习，坚持就是胜利，今日leetcode练习之相交链表。”

ps：今日涉及链表相关题目，在这里不对链表进行相关的介绍，不是很清楚的同学可以去网上搜索相关知识点做补充，之后再来看这道题。

1. 编写一个程序，找到两个单链表相交的起始节点

具体内容如下两幅图所示：

注意：

如果两个链表没有交点，返回 null.

在返回结果后，两个链表仍须保持原有的结构。

可假定整个链表结构中没有循环。

程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

2. 方法一之Set

思路：
链表在相交的时候，表示两个链表中各自存在一个节点指向同一个地址，那么这个时候我们可以考虑将A或者B链表中的一个存入到Set对象中（假如是将A链表存入到Set对象中），接着将B链表中第一个节点拿出来看是否在Set中，如果不在的话，那么使用next找寻B链表中第二个节点，然后重复上面过程，如果找到则返回该值，如果没有找到则返回null。
注意：使用Set原因：因为存储的是对象，即可以通过地址进行查找，具有唯一性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let set = new Set();
    while (headA) {
        set.add(headA);
        headA = headA.next;
    }
    while(headB) {
        if (set.has(headB)) return headB;
        headB = headB.next;
    }
    return null;
};

这个时候我们会发现问题：
headA循环中假设m次循环完，headB循环中假设n次循环完，由于不知m还是n大，则这个时候时间复杂度为O(m+n)，并且由于使用了Set，空间复杂度为O(m)或者O(n)，看你是循环添加headA还是循环添加headB。

2. 补差法

思路：
有一个消差法，由于代码比较冗余这边不做解析，有兴趣的小伙伴可以看我在文章结尾给的参考地址，里面有消差的解析。
补差的思路其实就是：A+B=B+A，下面盗用了一张画的图解析过程：

其实不难看出通过补差法它们会在第二次的时候相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let currentA = headA;
    let currentB = headB;
    while (currentA !== currentB) {
        currentA = currentA === null ? headB : currentA.next;
        currentB = currentB === null ? headA : currentB.next;
    }
    return currentA;
};

感谢这位大佬给的解析，参考链接如下所示：

掘金–相交链表(JS)