单链表之相交及交点

一、结点结构
        单链表的数据结构定义如下：
        typedef struct node
        {
            ElemType data;
            struct node *next;
        }list;
        其中，ElemType可以是任意数据类型如int、float或者char等，在算法中，规定其默认为int类型。

二、判断是否相交
        链表相交形态：
            （1）如果存在交点，则两个链表呈Y字形，而不是X形；
            （2）如果存在交点，则两个链表在交点及其之后的部分是重叠的，且长度和数据相同。
        判断是否相交的方法有多种，这里分链表本身有无环来介绍：
1、无环
        （1）是否有环
        原理：把一个链表的尾结点和另一个链表的首结点链接起来，然后判断是否有环（这个原理可以参考前文）即可，具体代码如下：
        bool iscross(list *head1, list *head2)
        {
            if ((NULL == head1) || (NULL == head2))
            {
                return false;
            }
            list *p1=head1;
            while (p1->next)
            {
                p1 = p1->next;
            }
            p1->next = head2;
            if (hascircle(head1))        // hascircle函数参考前文，在此直接引用
            {
                return true;
            }
            return false;
        }
        （2）尾结点相等
        原理：如果两个链表相交，则其尾结点必然相等（重叠），具体代码如下：
        bool iscross(list *head1, list *head2)
        {
            if ((NULL == head1) || (NULL == head2))
            {
                return false;
            }
            while (head1->next)
            {
                head1 = head1->next;
            }
            while (head2->next)
            {
                head2 = head2->next;
            }
            if (head1 == head2)
            {
                return true;
            }
            return false;
        }
2、有环
        原理：有环链表相交，必然有同一个环，可以用快慢指针解决，即在绕环n圈后，快指针必然遇到慢指针，具体代码如下：
        bool iscross(list *head1, list *head2)
        {
            if ((NULL == head1) || (NULL == head2))
            {
                return false;    
            }
            bool iscross = false;
            list *fast=head1, *slow=head2;
            while (fast && fast->next)
            {
                fast = fast->next->next;
                slow = slow->next;
                if (slow && (slow == fast))
                {
                    iscross = true;
                    break;
                }
            }
            return iscross;
        }

三、求两链表交点
        求环的起点原理与求是否有环类似，但需要额外步骤：用两个步长分别为1和2的指针遍历链表，直到两者相遇，此时慢指针走过的长度就是环的长度，相遇后把其中一个指针（比如：步长为2的指针）重新设定为起始点，让两个指针都以步长1再走一遍链表，相遇点就是环的起始点。推理证明步骤如下：
        第一次相遇时：
                慢指针走过的路程：S1 = 非环部分长度 + 弧A长
                快指针走过的路程：S2 = 非环部分长度 + n*环长 + 弧A长
                由S1*2 = S2可以得出：非环部分长度 = n*环长 - 弧A长
        让指针A回到起始点后，走过一个非环部分长度，指针B走过了相等的长度，也就是n*环长，正好回到环的开头。
        如果不能理解这些的话，可以从纯数学的角度来看此问题，即非环部分长度 = n*环长 - 弧A长，那就行了，具体算法如下：
        list *findintersection(list *head1, list *head2)
        {
            if ((NULL == head1) || (NULL == head2))
            {
                return NULL;
            }
            list *p1=head1, *p2=head2;
            int i=0, j=0, diff=0;
            while (NULL != p1->next)                    // 求链表1的长度
            {
                p1 = p1->next;
                i++;
            }
            while (NULL != p2->next)                    // 求链表2的长度
            {
                p2 = p2->next;
                j++;
            }
            if (p1 != p2)    // 相交则尾结点必定相同，否则不相交
            {
                return NULL;
            }
            else             // 相交则寻找第一个相同的交点
            {
                p1 = head1; 
                p2 = head2;
                // 使得两个链表的起始位置离尾部的距离一致
                if (i >= j)               
                {
                    diff = i - j;        // 算出两条链表的长度差值
                    // 长链表的指针向前移动差值个单位
                    for (int k=0; k                     {
                        p1 = p1->next;
                    }
                }
                else
                {
                    diff = j - i;
                    // 长链表的指针向前移动差值个单位
                    for (int k=0; k                     {
                        p2 = p2->next;
                    }
                }
                // 开始比较，如果相等则是第一个交点
                while (p1 != p2)
                {
                    p1 = p1->next;
                    p2 = p2->next;
                }
                return p1;
            }
        }
        如果无法理解上面的代码，可以看下图：

图1 链表相交

        两个链表相交后的Y型如上图1所示，而不是下图2：

图2 链表相交