判断两个链表是否相交可以用HashSet，但是HashSet需要额外的空间。所以这里使用双指针的解法。

160-相交链表

双指针1

这里有一个问题就是两条链表A和B可能不一样长，这样两个指针p1和p2不能同时指向相交节点c1上。 所以我们让p1遍历完链表A后再去遍历链表B，p2遍历完链表B之后去遍历链表A，这样两条链表就连接在了一起。这样拼接之后，就可以让p1和p2同时进入公共部分，也就是同时到达相交节点c1。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //p1只想链表A的头节点，p2指向链表B的头节点
    ListNode p1 = headA, p2 = headB;
    while(p1 != p2){
        // p1 走一步，如果走到 A 链表末尾，转到 B 链表
        if(p1 == null){
            p1 = headB;
        }else{
            p1 = p1.next;
        }
        // p2 走一步，如果走到 B 链表末尾，转到 A 链表
        if(p2 == null){
            p2 = headA;
        }else{
            p2 = p2.next;
        }
    }
    return p1;
}

双指针2

这种解法也是双指针，也很好理解。既然「寻找两条链表的交点」的核心是p1和p2两个指针同时到达相交节点c1，那么我们可以先计算两条链表的长度，让p1和p2到达尾部的距离相同来做到这第一点。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int lenA = 0, lenB = 0;
    //计算两条链表长度
    for(ListNode p1 = headA; p1 != null; p1 = p1.next){
        lenA++;
    }
    for(ListNode p2 = headB; p2 != null; p2 = p2.next){
        lenB++;
    }
    // 让 p1 和 p2 到达尾部的距离相同
    ListNode p1 = headA, p2 = headB;
    if(lenA > lenB){
        for(int i = 0; i < lenA - lenB; i++){
            p1 = p1.next;
        }
    }else{
        for(int i = 0; i < lenB - lenA; i++){
            p2 = p2.next;
        }
    }
    // 看两个指针是否会相同，p1 == p2 时有两种情况：
    // 1、要么是两条链表不相交，他俩同时走到尾部空指针
    // 2、要么是两条链表相交，他俩走到两条链表的相交点
    while(p1 != p2){
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}