两个链表是否相交问题

两个链表是否相交问题

给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。注意：可能会出现链式结构中出现环。

首先，判断单个链表是否成环，给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

很简单，快慢指针，如果成环，一定会在环内相遇，此时让fast=head，再各自一人走一步，一定会在成环位置相遇。

    public ListNode detectCycle(ListNode head) {
        if(head==null || head.next == null || head.next.next ==null){
            return null;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while(slow!=fast && fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if(slow==fast){
            fast = head;
            while(fast!=slow){
                fast = fast.next;
                slow = slow.next;
            }
            return fast; 
        }
        return null;
    }

下面分类讨论情况。

情况1，两个链表都不成环，即链表中没有环结构

cura和curb分别遍历自己的链表，并用n记录二者长度的差值。

之后，谁更长谁作cura，否则就为curb，长的先走n的长度，之后再一起走，一定会在相交位置相遇。

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cura = headA;
        ListNode curb = headB;
        int n = 0;
        while(cura.next!=null){
            cura = cura.next;
            n++;
        }
        while(curb.next!=null){
            curb = curb.next;
            n--;
        }
        if(cura!=curb){
            return null;
        }
        cura = n > 0 ? headA : headB;
        curb = cura==headA ? headB : headA;
        n = Math.abs(n);
        while(n-->0){
            cura = cura.next;
        }
        while(cura!=curb){
            cura = cura.next;
            curb = curb.next;
        }
        return curb;
    }

情况2：一个为空，一个不为空

即一个成环，一个不成环，很显然，这种情况一定不相交。

情况3：都不为空

即两个链表都成环，又分为三种情况

第一种：都成环，各自不相交

 第二种，在成环前相交

第三种，相交，且成环位置不相同

 

三种情况中，情况二最好区分，因为和环就没关系，他们是在成环之前就相交了，甚至可以并到没有环的情况，下面判断情况一三

此时，要么是两链表不相交，要么就是两个入环节点不相同，那么我让其中一个入环节点转一圈，如果在转圈途中，遇到了另一个入环节点，就是情况三，否则就是情况一：，请看代码 

    public static ListNode bothLoop(ListNode head1, ListNode loop1, ListNode head2, 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){
                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;
        }
    }