160. 相交链表

[GpingFeng]

160. 相交链表

思路

解法一：使用双指针法

• 使用指针 pA 指向 headA，指针 pB 指向 headB
• 遍历两个链表，一直到链表尾部，即为 null
• 将链表A指向链表B头部，链表B指向链表A头部，重新遍历，第二次如果相交，即为交叉点。若不想交，则都为 null
• 返回

代码如下:

var getIntersectionNode = function(headA, headB) {
    let pA = headA;
    let pB = headB;
    // 遍历两个链表，一直到链表尾部，即为 null 
    // 将链表A指向链表B头部，链表B指向链表A头部，重新遍历，第二次如果相交，即为交叉点。若没有，则不相交
    while (pB !== pA) { // 最后如果都没有相交，则同时为 null，结束
      pA = pA === null ? headB : pA.next;
      pB = pB === null ? headA : pB.next;
    }
    return pA;
};

复杂度分析

• 时间复杂度。O(n)
• 空间复杂度为 O(1)