链表相交问题

判断两个单向链表是否相交，并找出他们的交点。
这个问题我们分三种情况讨论：

一. 两个链表都不存在环

问题思路：

1. 遍历两个链表，在遍历的过程中进行比较，看节点是否相同。

2. 先遍历第一个链表到他的尾部，然后将尾部的next指针指向第二个链表。这样两个链表就合成了一个链表，判断原来的两个链表是否相交也就转变成了判断新的链表是否有环的问题了。 如果新的链表有环则第二个链表从头节点遍历一定存在环。

   
   图片.png
3. 如果两个没有环的链表相交，则这两个链表的尾节点一定相等。因此这种方式判断两个链表是否相交，就分别遍历两个链表到尾部，判断是否相等，如果相等就是相交，否则不相交。

图片.png

第三那种情况的代码实现思路：
假设第一个链表长度为len1，第二个问len2，然后找出长度较长的，让长度较长的链表指针向后移动|len1 - len2| (len1-len2的绝对值)，然后在开始遍历两个链表，判断节点是否相同即可。代码如下

//链表节点的定义
typedef struct Node {
    int data;
    struct Node *pNext;
} NODE, *PNODE;


PNODE *findNode(PNODE head1, PNODE head2) {

    if (head1 == NULL || head2 == NULL) {
        //如果链表为空则很定不相交
        return NULL;
    }
    PNODE p1, p2;
    p1 = head1;
    p2 = head2;
    int len1 = 0; //第一个链表的长度
    int len2 = 0; //第二个链表的长度
    int diff = 0;
    while (NULL != p1->pNext) {
        p1 = p1->pNext;
        len1++;
    }
    while (NULL != p2->pNext) {
        p2 = p2->pNext;
        len2++;
    }
    if (p1 != p2) {
        //如果最后一个节点不相同则返回NULL
        return NULL;
    }
    diff = abs(len1 - len2);
    if (len1 > len2) {
        p1 = head1;
        p2 = head2;
    } else {
        p1 = head2;
        p2 = head1;
    }
    for (int i = 0; i < diff; i++) {
        p1 = p1->pNext;
    }
    while (p1 != p2) {
        p1 = p1->pNext;
        p2 = p2->pNext;
    }
    return p1;
}

二. 如果一个链表中有环，另一个链表没有环。

这种情况则两个链表一定不相交。因为一旦相交则另一个链表，一定存在环。

图片.png

三. 链表中有环

1. 判断链表是否存在环，办法为：设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则为无环链表)程序如下：

bool IsExitsLoop(slist *head){
    slist *slow = head, *fast = head;
    while ( fast && fast->next )     {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;
    }
    return !(fast == NULL || fast->next == NULL);
}

二、找到环的入口点当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：2s = s + nrs= nr设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。a + x = nra + x = (n – 1)r +r = (n-1)r + L - aa = (n-1)r + (L – a – x)(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。程序描述如下：

slist* FindLoopPort(slist *head){
    slist *slow = head, *fast = head;
    while ( fast && fast->next )     {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;
    }    if (fast == NULL || fast->next == NULL)
        return NULL;    slow = head;
    while (slow != fast)    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}