单链表判交问题，即是否有环，且环入口点,且两条链表是否相交

/// 单链表判交问题，即是否有环，且环入口点,判断两个单链表是否相交

#include <stdio.h>

#include <malloc.h>

typedef struct Node

{

    int data;

Node *next;

}Node;

/// @bried 判断是否有环

bool IsExitLoop(Node *head)

{

    Node *slow = head;

Node *fast = head;

while(fast && fast->next)

{

   slow = slow->next;

fast = fast->next->next;

/// 两个指针从头开始走，一个走一步，一个走两步

/// 单链表存在环，就一定会相遇。

        if(slow == fast)

        {

            break;

}

}

return !(NULL == fast || NULL == fast->next);

}

/// @brief 有环时，找到环的入口点。

Node *LoopEntryPoint(Node *head)

{

    Node *slow = head;

Node *fast = head;

Node *first;

Node *crossPoint;

while(fast && fast->next)

{

        slow = slow->next;

fast = fast->next->next;

/// 两个指针从头开始走，一个走一步，一个走两步

/// 单链表存在环，就一定会相遇。

/// 判断是否有环，且得出这两个指针在环中的相遇点

if(slow == fast)

{

            break;

}

}

if(NULL == fast || NULL == fast->next)

{

        return NULL;

}

    first      = head;

crossPoint = fast;

/*// 一个指针从头开始一步的移动，另一个从之前两个指针在环中的相遇点

/// 开始一步的移动，

/

    当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n即至少一圈)。

    假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，

    因为在相遇点，相对于此点fast也至少走了一圈，即至少是第二次通过此点。

    从此相遇点到链表的头与slow所走距离一样，即s

    所以:2s = s + nr

    即:  s= nr

    

    设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。

    a + x = nr     //a+x这是slow走的路程,即s

    a + x = (n – 1)r +r = (n-1)r + L - a  

    a = (n-1)r + (L – a – x)

    (L – a – x)为相遇点到环入口点的距离，

    由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，

    于是我们从链表头、与相遇点分别设一个指针，每次各走一步，

    两个指针必定相遇，且相遇第一点为环入口点。

*/

    while(first != crossPoint)

    {

first      = first->next;

crossPoint = crossPoint->next;

    }

return first;

}

/// @brief 判断两个单链表是否相交，且得出相交点

/*如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，

  我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以

  走到同样的结尾点，则两个链表相交。这时我们记下两个链表length，再

  遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链

  表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

*/

Node *TwoListIntersecting(Node* head1,Node* head2)

{

    int i;

    int lenth1 = 0;

int lenth2 = 0;

int len = 0;

    Node *L1 = head1;

Node *L2 = head2;

while(NULL != L1->next)

{

        L1 = L1->next;

lenth1++;

}

while(NULL != L2->next)

{

        L2 = L2->next;

lenth2++;

}

if(L1 != L2)

{

        fprintf(stdout,"they are not intersecting\n");

return NULL;

}

    L1 = head1;

    L2 = head2;

if(lenth1 >= lenth2)

{

        len = lenth1 - lenth2;

for(i=0; i<len; i++)

{

            L1 = L1->next;

}

}

else if(lenth1 < lenth2)

{

        len = lenth2 - lenth1;

for(i=0; i<len; i++)

{

            L2 = L2->next;

}

}

while(L1 == L2)

{

   L1 = L1->next;

        L2 = L2->next;

}

return L1;

}

Node *CreateLoopList()

{

    int i;

    Node *tmp,*current,*pLoop;

Node *head = (Node *)malloc(sizeof(Node));

    head->data = 0;

head->next = NULL;

    tmp = head;

    for(i=0; i<10; i++)

    {

        current = (Node *)malloc(sizeof(Node));

current->data = i;

if(5 == i)

{

            pLoop = current;

}

current->next = tmp->next;

tmp->next = current;

tmp = current;

current = NULL;

}

#if 0

    /// @brief 设置环节点

current = (Node *)malloc(sizeof(Node));

current->data = i;

current->next = pLoop;

tmp->next = current;

tmp = current;

current = NULL;

#endif

return head;

}

void printfList(Node* head)

{

    Node *tmp = head;

    while(tmp->next)

    {

        printf("data[%d]\n",tmp->next->data);

tmp = tmp->next;

}

}

int main(int argc,char *argv[])

{

    int flag;

Node *tmp  = NULL;

    Node *head = NULL;

    Node *tt   = NULL;

    Node *xx   = NULL;

    head = CreateLoopList();

printfList(head);

    flag = IsExitLoop(head);

if(flag == true)

{

   printf("have loop\n");

}

else

{

        printf("have no loop\n");

}

    xx = LoopEntryPoint(head);

//printf("the loop entry point data[%d]\n",tmp->data);

tmp = CreateLoopList();

    printfList(tmp);

tt = TwoListIntersecting(tmp, head);

if(NULL == tt)

{

        fprintf(stdout,"have no crossing\n");

}

else

{

        fprintf(stdout,"yes a crossing data[%d]\n",tt->data);

}

return 0;

}