相交链表

思路： 方法一： 判断两个链表是否相交，可以使用哈希集合存储链表节点。首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中。 方法二： 使用双指针去遍历A链表和B链表。 当链表headA 和headB 都不为空时，创建两个指针pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下： 每步操作需要同时更新指针 pA 和 pB。 如果指针 pA 不为空，则将指针pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。 如果指针pA 为空，则将指针pA 移到链表 headB 的头节点；如果指针pB 为空，则将指针 pB 移到链表 headA 的头节点。 当指针pA 和pB 指向同一个节点或者都为空时，返回它们指向的节点或者null。 原理： 假设A未相交部分为a，B未相交部分为b，相交部分未c 。 在指针 pA 移动了 a+c+b次、指针 pB 移动了b+c+a 次之后，两个指针会同时到达两个链表相交的节点。

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pointA = headA;
        ListNode pointB = headB;
        while (pointA != pointB) {
            pointA = pointA == null ? headB : pointA.next;
            pointB = pointB == null ? headA : pointB.next;
        }
        return pointA;
    }

思路： 假设一个快指针 fast （每次移动2格）和慢指针 slow （每次移动1格） fast = 2slow 假设b点时第一次相遇 这时 2（a+b） = a+n(b+c)+b ==》 a = c +(n-1 )(b+c) 此时当发现 slow 与fast 相遇时，我们再额外使用一个指针ptr，ptr 速度和 slow 相同。 这时，当ptr 走到入环点的时候，slow 走了 c +(n-1 )(b+c)的距离，正好在入环点相遇。

public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode p = head;
        boolean hasCycle = false;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                hasCycle = true;
                break;
            }
        }
        if (hasCycle) {
            while (p != slow) {
                p = p.next;
                slow = slow.next;
            }
        }
        return slow;
    }