本文共 1124 字，大约阅读时间需要 3 分钟。

方法一：双指针

假设两个链表公共长度为C,不公共的长度分别为A、B。 则两个链表长度分别为A+C，B+C。 设两个指针，让第一个链表走完之后，跳到第二个链表开始走，共A+C+X1距离；同理第二个链表走完后调到第一个链表开始走，走B+C+X2距离。

那么两个指针相遇时，由 A+C+X1 = B+C+X2，距离不为负，得X1=B，X2=A，所以最后两个指针走的距离都是A+B+C，刚好在第一个公共点相遇。

复杂度分析

时间复杂度 : O(m+n)

//双指针var getIntersectionNode = function(headA, headB) {    let node1 = headA, node2 = headB;    while(node1 != node2) {        node1 = node1 !== null ? node1.next : headB;        node2 = node2 !== null ? node2.next : headA;    }    return node1;  //这里写node2结果也一样};

方法二：Hashmap

第一个while循环遍历第一个链表，将其所有节点放入 map 中

• has()方法: 判断Map对象中是否存在指定元素。如果具有指定元素则返回true，否则返回false。
• set()方法: 为Map对象添加一个指定键（key）和值（value）的新元素。
• get()方法: 用来获取一个 Map对象中指定的元素。

//hashmap法var getIntersectionNode2 = function(headA, headB) {    let map = new Map();    while(headA) {        map.set(headA, true);        headA = headA.next;    }    while(headB) {        if(map.has(headB)) //找到了第一个公共结点            return headB;        headB = headB.next;    }    return null;};

ES6中增加了Map和Set两种新的数据结构

• Map是类似Object的一种键值对集合，区别在于Map的键不仅限于是字符串，其他各种类型的值包括对象都可以成为Map的键
• Set是类似数组的一种数据结构，不同点在于Set中没有重复的值

转载地址：http://vnuvi.baihongyu.com/