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

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
    }