[数据结构与算法]Day6 链表-判断相交

链表相交

今天是链表的比较难的一个算法，判断两个链表第一个相交的位置在哪，如果有相交返回相交的那个节点；如果没有相交则返回空。

首先，我们要把判断分成几个情况。

一、有环和无环

显然，有环和无环两种情况，对链表判断相交与否肯定有影响。如果有环就返回环的入口，如果没环就返空。那么我们要先判断两个链表是否有环。要判断有环和无环我们依旧可以使用快慢指针。

让快指针和慢指针一起走，如果快指针能走到null，那么显然没有环，如果快指针和慢指针最终相遇了。

复杂的算法证明：当慢指针走到环的入口是，慢指针走了环外长度 x 步，而快指针走了x + n圈y长度的环的步数+d环内多走了几步?。那么 x ==? ny + d，因为快指针比慢指针在环内多走了d步。因此，快指针要再走y-d步才能和慢指针相遇，又因为快指针一次走两步，所以快指针在环内还要再走 2（y-d）步；那么快指针再次追上慢指针是在 2（y-d） + d = 2y -d 也就是快指针是走了2圈退d步，也就是在环入口节点往逆环方向走d步。

可以发现，这个时候快指针的位置和慢指针刚进环时候的快指针当时的位置是对称的。

那么，只要在快慢指针相遇时，把快指针放回head节点，再两个指针一起动，此时两个指针都一次走一格。那么此时快指针走了：x步， 由前面x == ny + d 会发现，此时慢指针恰好走了n圈，并再走了d步回到入口。

结论：快慢指针从head一起出发，当两个指针在环内相交时，把快指针再指向头节点。再让两个指针以一次一步同速走，那么两个指针再次相遇的地点就是环的入口。

证明的链接

方法代码：

     //获得链表环的入环节点，如果没环返回空
        static Node GetLoopNode(Node head)
        {
            if(head ==null || head.next ==null || head.next.next == null)
            {
                return null;
            }
            Node f = head;
            Node s = head;
            f = f.next.next;
            s = s.next;
            //一直走直到指针相遇
            while (s != f)
            {
                //如果快指针走到null就返回null表示无环
                if(f.next == null || f.next.next == null)
                {
                    return null;
                }
                s = s.next;
                f = f.next.next;
            }
            //让快指针回到头节点
            f = head;
            //继续遍历，两个指针一定会在环的入环点相遇
            while (s != f)
            {
                s = s.next;
                f = f.next;
            }
            return s; 
        }

二、都有环和都没环

很显然，一个有环一个没环是不可能有交点的，直接返回空

那么接下来讨论都有环和都没环的情况：

1）都没环

都没环意味着两个链表都能走到最后，也就是我们能算得出来两个链表的长度和最后一位。

如果练个链表相交，两个链表必然会有公共部分，设链表1的前半部分长度是a,链表2是b，两个后半部分长度都是是c

那么显然，a+c - （b+c）就是两个链表长度的差值绝对值，要想算出两个链表的交点只需要让长的链表先走差值的部分再让两个链表一起走，那么两个链表必然会同时走到第一个交点，就假设，a是5，b是3，c是8，那么如果a先走了2步再两个一起走3步，必然会同时走到两个的交点，只要判断指针是否一样就可以知道哪个点是第一个交点了。

如果两个链表没有交点，这个只要在计算两个链表长度的时候比对一下最后一个节点的指针是否相等，如果不等一定没有交点。

代码：

 //获得无环链表的第一个交点
        static Node GetNoLoopNode(Node head1,Node head2)
        {
            Node n1 = head1;
            Node n2 = head2;
            int n = 0;
            while (n1.next != null)
            {
                n++;
                n1 = n1.next;
            }
            while (n2.next != null)
            {
                n--;
                n2 = n2.next;
            }
            //如果两个指针走到尾不相等那么不可能相交
            if(n1 != n2)
            {
                return null;
            }
            n1 = n > 0 ? head1 : head2;
            n2 = n1 == head1 ? head2 : head1;
            n = Math.Abs(n);
            while (n != 0)
            {
                n1 = n1.next;
                n--;
            }
            while (n1 != n2)
            {
                n1 = n1.next;
                n2 = n2.next;
            }
            return n1;
        }

2）都有环

都有环的话，如果有交点分成俩情况：

1、交点在环外。因为我们已经知道两个链表都有环，那么我们只要用前面的函数来分别得到两个链表入环的点。既然点在环外，那么两个链表入环点是一样的，我们只要吧这个入环点当成两个链表的终点（把两个有环链表当成无环的来看，终点变成入环点）。这样的话，我们只要按照两个都无环的情况来处理就好。

2、交点在环内。我们只要让两个链表的其中一个在loop1直接继续走，如果走一圈环而没有碰到另一个链表的loop2，那么两个链表没交点，如果走了一圈碰到了loop2则表示有交点并返回那个点。

代码：

    //获得有环链表的第一个交点
        static Node GetBothLoopNode(Node head1,Node loop1, Node head2,Node loop2)
        {
            Node n1 = null;
            Node n2 = null;
            //当两个链表的入环点是一样时 判断在哪入的环
            if (loop1 == loop2)
            {
                n1 = head1;
                n2 = head2;
                //n来记录两个链表从head到入环的走的长度的差
                int n = 0;
                while (n1.next != loop1)
                {
                    n++;
                    n1 = n1.next;
                }
                while (n2.next != loop2)
                {
                    n--;
                    n2 = n2.next;
                }
                //让n1代表长的一个链表
                n1 = n > 0 ? head1 : head2;
                n2 = n1 == head1 ? head2 : head1;
                n = Math.Abs(n);
                //让长的链表先走n的距离 再一起走 什么时候指针相同，那就是第一个交点
                while (n != 0)
                {
                    n--;
                    n1 = n1.next;
                }
                while (n1 != n2)
                {
                    n1 = n1.next;
                    n2 = n2.next;
                }
                return n1;
            }
            else
            {
                //让n1指向loop1的下一位，然后持续遍历直到n1走到loop2
                n1 = loop1.next;
                while(n1 != loop1)
                {
                    if(n1 == loop2)
                    {
                        return n1;
                    }
                    n1 = n1.next;
                }
                return null;
            }
            return null;
        }

下面是整合之后的函数代码：

     //获得两个链表的第一个交点 没有就返回空
        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)
            {
                return GetNoLoopNode(head1, head2);
            }
            if(loop1 != null && loop2 != null)
            {
                return GetBothLoopNode(head1,loop1, head2,loop2);
            }
            return null;
        }

昨天国庆，比较摸嘿嘿！

如果有写的不好的或者有错的地方、望指正，如果我的自我监督学习记录有帮到你的话就好！