[leetcode]No.160 相交链表（双指针解法）

[liangbus]

160. 相交链表

其实这道题是一道简单的题，解法不止一种，很容易就想到暴力和使用 hash 来解，不过题目最后要求，尽量不使用额外空间去解，所以这里着重介绍的就是双指针解法

最初学习双指针是在回文数的例子上，这里的双指针跟回文的又有点不一样。

假设为 A, B 链表，A, B两个链表长度可能不是一致的，但是 length(A) + length(B) 和 length(B) + length(A)肯定是一样的，这是很关键的信息，假设遍历 A，B 链表的指针分别为 pA 和 pB ，当 pA 遍历到链表的末端时，将其指向另外一个链表的头指针，pB 同理，如此反复，假如链表相交，总会出现相同的结点，否则，两个指针同时到达两个链表的末端

var getIntersectionNode = function(headA, headB) {
    if(!headA || !headB) return null
    let curANode = headA
    let curBNode = headB
    while(curANode !== curBNode) {
        if(!curANode.next && !curBNode.next) return null
        curANode = curANode.next ? curANode.next : headB
        curBNode = curBNode.next ? curBNode.next : headA
    }
    return curANode
};