题目

给定两个可能有环也可能无环的单链表，头节点 head1 和 head2。请实现一个函数，如果两链表相交，请返回相交的第一个节点，不相交返回null。要求：如果两链表长度之和为N，时间复杂度为O(N)，额外空间复杂度为O(1)。

题解

• 首先判断两链表有无环，如果有环则求出入环点
• 如果两链表均无环则有以下两种情况

先分别求出两个链表的尾节点，如果不同则不相交。如果相同则设两指针分别指向两链表头节点，长链表的指针先走长度之差步，然后两链表指针同时走，直至相遇，此时指针所指节点即为第一个相遇节点。

• 如果两链表均有环则有以下三种情况

若两链表入环点相同即情况2，则类似与两无环链表情况。计算两链表到入环点的长度之差，长链表的指针先走长度之差步，然后两链表指针同时走，直至相遇，此时指针所指节点即为第一个相遇节点。

若两链表入环节点不同则可能有情况1和情况3。从其中一个链表的入环点开始走，若走完一圈还没碰到另一个链表的入环点则情况1，不相交；若在走完一圈之前碰到了另一个链表的入环点，则为情况3，此时两个入环点均可以是第一个相遇点。

• 如果一个有环一个无环，则必不相交

代码实现

public class FindFirstIntersectNode {
    //求第一个相交节点，没有返回null
    public static Node getFirstIntersectNode(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node loop1 = getLoopNode(head1); //求链表1的入环点
        Node loop2 = getLoopNode(head2); //求链表2的入环点
        if (loop1 == null && loop2 == null) { //两无环链表
            return noLoop(head1, head2);
        }
        if (loop1 != null && loop2 != null) { //两有环链表
            return bothLoop(head1, loop1, head2, loop2);
        }
        //一个有环一个无环一定无相交节点
        return null;
    }

    //找到链表的第一个入环点，如果无环返回null
    public static Node getLoopNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Node n1 = head.next; //慢指针
        Node n2 = head.next.next; //快指针
        while (n1 != n2) {
            if (n2.next == null || n2.next.next == null) {
                return null;
            }
            n2 = n2.next.next;
            n1 = n1.next;
        }
        n2 = head;
        while (n1 != n2) {
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;
    }

    //两链表均无环的情况，返回第一个相交节点，如果不相交返回null
    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 = Math.abs(n);
        while (n != 0) { //长链表先走差值步
            n--;
            cur1 = cur1.next;
        }
        while (cur1 != cur2) { //两链表同时走直至相遇
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
    //两个有环链表，返回第一个相交节点，如果不相交返回null
    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;
            cur2 = cur1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while (n != 0) {
                n--;
                cur1 = cur1.next;
            }
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        } else { //入环点不同，从一个入环节点开始走一圈，遇到另一个入环节点即相交
            cur1 = loop1.next;
            while (cur1 != loop1) {
                if (cur1 == loop2) {
                    return loop1;
                }
                cur1 = cur1.next;
            }
            //没遇到即不相交
            return null;
        }
    }
    //测试节点
    class Node{
        int value;
        Node next;

    }
}