【常见面试算法】相交链表

问题

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

思路

解题思路：
1）如何判断单链表有环；
2）如何判断无环单链表的相交节点；
3）有环单链表的相交节点。

解题方法：
1）用Hashset判断是否有环，当hashset中查到已存在节点，则该节点为环的入口；
2）若不用hashset，准备快慢指针。快指针为空则无环，若有环，快慢指针一定会在环上相遇。相遇后，快指针回到头节点，变为一次走一步，则两个指针一定会在入口相遇。
3）若无环，如何判断相交的第一个节点？可以用hashset存list1的节点，遍历list2时去遍历hashset，若list2遍历完了还没查到，就不相交。若不用hashset，统计list1和list2的长度，以及两者end节点是否相等（内存地址是否相等，而不是值相等），若相等说明必相交，否则不相交。使较长的的list在两者长度差的地方开始遍历，最终找到相交节点。

两个有环链表的拓扑结构：
1）各自为环，且不相交；
2）先相交，再入环；
3）环一样，但入口不同；
图片说明

如何区别三种拓扑结构？
定义head1、head2、loop1、loop2，若loop1=loop2则为第二种，此时问题变回单链表相交问题，不用考虑环了；loop1不等于loop2，则可能为1也可能为3，此时，让loop1不断next，若找到等于loop2的节点，则为第三种，此时返回loop1或者loop2都是正确的，若loop1转了一圈还未找到loop2，则为第一种。

梳理：
1）先判断链表是否有环，若一个有一个没有，返回null；
2）若两个都无环，则为单链表问题；
若两个都有环，则先确定二者的环入口，再回到判断两个有环链表拓扑结构问题。

package 左神算法班实现.初级班.后四节课;

public class 链表相交 {
    public static ListNode isCross(ListNode head1, ListNode head2){
        if (head1 == null || head2 == null){
            return null;
        }
        //判断是否为无环链表
        ListNode loop1 = hasLoop(head1);
        ListNode loop2 = hasLoop(head2);

        if (loop1 == null && loop2 == null){//两个都是无环链表
            return bothNotLoop(head1,head2);
        }
        if (loop1 != null && loop2 != null){
            return bothLoop(head1, head2, loop1, loop2);
        }
        return null;
    }

    public static ListNode hasLoop(ListNode head){

        if (head == null || head.next == null || head.next.next == null) return null;

        ListNode fast = head.next.next;
        ListNode slow = head.next;

        while (fast != slow){
            if (fast.next == null || fast.next.next == null){
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        fast = head;
        while (fast != slow){
            slow = slow.next;
            fast = fast.next;
        }

        return fast;
    }

    public static ListNode bothNotLoop(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) return null;
        ListNode h1 = head1;
        ListNode h2 = head2;
        int n = 0;
        while (h1.next != null) {
            n++;
            h1 = h1.next;
        }
        while (h2.next != null) {
            n--;
            h2 = h2.next;
        }

        h1 = n > 0 ? head1 : head2;
        h2 = h1 == head1 ? head2 :head1;
        n = Math.abs(n);

        while (n > 0){
            n--;
            h1 = h1.next;
        }
        while (h1 != h2){
            h1 = h1.next;
            h2 = h2.next;
        }
        return h1;
    }

    public static ListNode bothLoop(ListNode head1, ListNode head2, ListNode loop1, ListNode loop2){
        ListNode cur1 = null;
        ListNode 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;
            while (cur1 != loop2){
                cur1 = cur1.next;
                if (cur1 == loop1){//loop1转了一圈还没有找到与loop2相等的节点，说明不是同一个环
                    return null;
                }
            }
            return loop1;
        }
    }

    public static void main(String[] args) {
        // 1->2->3->4->5->6->7->null
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        head1.next.next.next.next.next = new ListNode(6);
        head1.next.next.next.next.next.next = new ListNode(7);

        // 0->9->8->6->7->null
        ListNode head2 = new ListNode(0);
        head2.next = new ListNode(9);
        head2.next.next = new ListNode(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(isCross(head1, head2).val);

        // 1->2->3->4->5->6->7->4...
        head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        head1.next.next.next.next.next = new ListNode(6);
        head1.next.next.next.next.next.next = new ListNode(7);
        head1.next.next.next.next.next.next = head1.next.next.next; // 7->4
        //System.out.println(hasLoop(head1).val);

        // 0->9->8->2...
        head2 = new ListNode(0);
        head2.next = new ListNode(9);
        head2.next.next = new ListNode(8);
        head2.next.next.next = head1.next; // 8->2
        System.out.println(isCross(head1, head2).val);

        // 0->9->8->6->4->5->6..
        head2 = new ListNode(0);
        head2.next = new ListNode(9);
        head2.next.next = new ListNode(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(isCross(head1, head2).val);
    }
}