一、返回单向有环链表中第一个入环的节点：

1.方法一：使用set。

思路：如果有环，那么遍历链表，某个节点被遍历到第二次的时候他就是第一个入环的节点。
使用set,遍历加入set，若某个节点之前被添加过了（第一次重复），将这个节点返回。

2.方法二：使用快慢指针。

1）慢指针slow（一次走一步），快指针fast（一次走两步）；慢指针从head.next出发，快指针从head
next.next出发。开始遍历，在第一次两个指针相遇时，停止（表名此时链表内是有环的）。
2）然后让快指针回到head，变为一次走一步，慢指针维持在原地，保持一次走一步，他们一定会在第一个入环的节点相遇。返回这个节点。

//使用HashSet
    public ListNode EntryNodeOfLoop(ListNode head) {
        if(head == null || head.next == null || head.next.next==null) return null;
        HashSet<ListNode> set = new HashSet<>();
        ListNode cur = head;
        while(cur != null){
            if(set.add(cur)){
                cur = cur.next;
            }else{
                return cur; //代表有环，且cur就是入环节点
            }
        }//while循环退出，表示无环，并且此时cur已经指向的是链表的结尾的next，也就是null，返回即可
        return cur;
    }

//使用快慢指针
public static Node getLoopNode(Node head){
    if(head == null || head.next == null || head.next.next == null) return null;
    Node slow = head.next;
    Node fast = head.next.next;
    while(slow != fast){
        if(fast.next == null || fast.next.next == null){
            return null;
        }
        fast = fast.next.next;
        slow = slow.next;
    }
    //上面while循环结束表示链表中有环，并且fast == slow
    fast = head; // 重置fast
    while(slow != fast){
        slow = slow.next;
        fast = fast.next;
    }
    return slow; //最后相遇的位置就是第一个入环的节点
}

二、链表相交问题：

目标：找到相交的第一个节点，并返回，若不相交，返回null。

1.两个无环链表：

【思路】：1）若相交。相交之后的部分一定是共用的。因为单链表只有一个next指针。
方法一：使用set。思路与上述找有环链表的入环节点相同。
方法二：长链表先走比短链表多出来部分，然后再一起走，第一个相同的节点就是相交的位置。
2）若不相交。遍历两条链表至最后，若结尾不相同，则两条链表不相交。

【整理】：
1）首先判断链表是否相交。遍历两条链表至最后，若结尾不相同，则两条链表不相交。不相交，就返回null，若相交，进入下一步。
2）根据思路的方法二（代码如下）。（也可以使用思路的方法一）

    public static Node noLoop(Node head1, Node head2){
        if (head1 == null || head2 == null) return null;

        Node cur1 = head1;
        Node cur2 = head2;
        int n = 0;
        while (cur1.next != null){
            n++;
            cur1 = cur1.next;
        }
        while (cur2.next != null){
            n--;
            cur2 = cur2.next;
        }
        if (cur1 != cur2){
            return null; // 说明没有相交
        }

        cur1 = n > 0 ? head1 : head2; //将长链表的头给cur1
        cur2 = cur1 == head1 ? head2 : head1; // 将短链表的 头，给cur2 

        //n为两个链表长度的差值
        n = Math.abs(n);
        while (n != 0){//cur1先走
            n--;
            cur1 = cur1.next;
        }

        while (cur1 != cur2){//cur1和cur2一起走，直到相遇结束
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

2.一个无环链表和一个有环链表是不可能相交的。

3.两个有环链表：两个有环链表相交，则他们一定共用这个环。

这种情况下：问题转化为求无环链表的相交节点。

情况三：入环节点是两个，但各自成环，即不相交，返回null。

思路：先去判断属于哪种情况然后在处理相交。

    //两个有环链表，返回第一个相交节点，没有返回null。loop为链表的入环节点。
    public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2){
        Node cur1 = null;
        Node cur2 = null;

        //第一种情况
        if (loop1 == loop2){
            cur1 = head1;
            cur2 = head2;
            int n = 0;
            while (cur1 != loop1){
                n++;
                cur1 = cur1.next;
            }
            while (cur2 != loop2){
                n--;
                cur2 = cur2.next;
            }
            cur1 = n > 0 ? head1 : head2; //将长链表的头给cur1
            cur2 = cur1 == head1 ? head2 : head1; // 将短链表的 头，给cur2
            //n为两个链表长度的差值
            n = Math.abs(n);
            while (n != 0){//cur1先走
                n--;
                cur1 = cur1.next;
            }
            while (cur1 != cur2){//cur1和cur2一起走，直到相遇结束
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }else {//相交的节点不相等
            cur1 = loop1.next;
            while (cur1 != loop1){//从入环节点开始，若转回到自己，则说明不相交，返回null
                if (cur1 == loop2){
                    return loop1;//loop1、loop2都是相交的节点
                }
                cur1 = cur1.next;
            }
            return null;
        }
    }

主方法：

    public static Node getIntersectNode(Node head1, Node head2){
        if (head1 == null || head2 == null){
            return  null;
        }
        //获得两个链表的入环节点
        Node loop1 = getLoopNode(head1);
        Node loop2 = getLoopNode(head2);
        if (loop1 == null && loop2 == null){
            //如果都为空，表明他们都为非带环链表，使用方法noLoop()处理；    
            return noLoop(head1,head2);
        }
        //如果都不为空，表明他们都为带环链表，使用方法bothLoop()处理；
        if (loop1 != null && loop2 != null){
            return bothLoop(head1,loop1,head2,loop2);
        }
        return null; //剩下情况直接返回null
    }