160. 相交链表的相交结点

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：

/**
 * 利用哈希表
 *
 * @param headA
 * @param headB
 * @return
 */
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Set<ListNode> headASet = new HashSet<>();
    while (headA != null) {
        headASet.add(headA);
        headA = headA.next;
    }
    while (headB != null) {
        if (headASet.contains(headB)) {
            return headB;
        }
        headB = headB.next;
    }
    return null;
}

如果不借用哈希表，那么则需要借助双指针来实现

由于两条链表的长度可能不同，两条链表之间的节点无法对应：

如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点 c1。

解决这个问题的关键是，通过某些方式，让 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;
    ListNode 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;
}