/***/面试题：求相交链表的交点

45 阅读 0 评论 30 点赞

我是靠谱客的博主想人陪小伙，最近开发中收集的这篇文章主要介绍/***/面试题：求相交链表的交点，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链表相交的情况，如图：
这里写图片描述
方法一

分别统计两条链表的长度s1和s2，假设s1大于s2，则我们让head1先走上s1-s2步，让后再让head2也出发，则它们的相遇点就是交点。

pLinkNode GetEntryCycle(pLinkNode head, pLinkNode meet)  
{  
    pLinkNode cur = head->next;  
    pLinkNode pmeet = meet;  
    while (pmeet != cur)             //求环的入口点  
    {  
        pmeet = pmeet->next;  
        cur = cur->next;  
    }  
    while (cur->next != pmeet)        //找到环中入口的前一个结点  
    {  
        cur = cur->next;  
    }  
    return cur;  
}  


//转化成不带环的链表求解  
pLinkNode NotCycleCrossPoint(pLinkNode head1,pLinkNode head2)       
{  
    pLinkNode list1 = head1->next;  
    pLinkNode list2 = head2->next;  
    int count1 = 0;  
    int count2 = 0;  
    while (NULL!=list1)   //求head1的表长  
    {  
        count1++;  
        list1 = list1->next;  
    }  
    while (NULL != list2)   //求head2的表长  
    {  
        count2++;  
        list2 = list2->next;  
    }  
    list1 = head1->next;  
    list2 = head2->next;  
    int len = count1 - count2;  
    if (len > 0)  
    {  
        while (len--)  
        {  
            list1=list1->next;  
        }  
    }  
    else if (len<0)  
    {  
        len = -len;  
        while (len--)  
        {  
            list2 = list2->next;  
        }  
    }  
    while (list1 != list2)        //求取交点  
    {  
        list1 = list1->next;  
        list2 = list2->next;  
    }  
    return list1;  
}  

//在两个链表已经相交的前提下，转化成不带环的链表求解  
pLinkNode GetCycleCrossPoint(pLinkNode head1, pLinkNode head2)  
{  
    pLinkNode meet1 = NULL;  
    pLinkNode meet2 = NULL;  
    pLinkNode ret = NULL;  
    meet1=GetCycleMeet(head1);  
    meet2=GetCycleMeet(head2);  
    if ((meet1 == NULL) && (meet2 == NULL))       //如果两个链表都不带环,则直接求解  
    {  
        ret=NotCycleCrossPoint(head1,head2);  
    }  
    else if (meet1&&meet2)                    //如果两个链表都带环  
    {  
        pLinkNode endNode= NULL;  
        pLinkNode cur = NULL;  
        endNode=GetEntryCycle(head1,meet1);      //找到环入口的前一个结点  
        cur = endNode->next;                       //保存环的入口  
        endNode->next = NULL;                      //将环断开拆分成两个不带环的链表  
        ret = NotCycleCrossPoint(head1,head2);        //获得交点  
        endNode->next = cur;                         //复原链表  
    }  
    return ret;  
}

方法二
这里写图片描述

这里写图片描述

//求相交链表的相交点  
pLinkNode GetEntryCycle(pLinkNode head, pLinkNode meet)  
{  
    pLinkNode cur = head->next;  
    pLinkNode pmeet = meet;  
    while (pmeet != cur)             //求环的入口点  
    {  
        pmeet = pmeet->next;  
        cur = cur->next;  
    }  
    while (cur->next != pmeet)        //找到环中入口的前一个结点  
    {  
        cur = cur->next;  
    }  
    return cur;  
}  

pLinkNode GetCycleMeet(pLinkNode head)      //判断链表是否带环，若带环则返回相遇点  
{  
    pLinkNode fast = head->next;  
    pLinkNode slow = head->next;  
    pLinkNode meet = NULL;  
    while (fast&&fast->next)           //判断链表head1是否带环  
    {  
        fast = fast->next->next;  
        slow = slow->next;  
        if (fast == slow)  
        {  
            meet = fast;  
            break;  
        }  
    }  
    return meet;  
}  


//在两个链表已经相交的前提下,转换成带环链表求解  
pLinkNode GetCycleCrossPoint(pLinkNode head1, pLinkNode head2)  
{  
    pLinkNode endNode = NULL;  
    pLinkNode cur = NULL;  
    pLinkNode meet1 = NULL;  
    pLinkNode meet2 = NULL;  
    pLinkNode ret = NULL;  
    meet1 = GetCycleMeet(head1);  
    meet2 = GetCycleMeet(head2);  
    if ((meet1 == NULL) && (meet2 == NULL))       //如果两个链表都不带环,则转换成带环链表  
    {  
        cur = head1->next;  
        while(NULL != cur->next)                  //找到最后一个结点  
        {  
            cur = cur->next;  
        }  
        cur->next = head2->next;                  //构造一个环  
        meet1 = GetCycleMeet(head1);              //获取环的相遇点  
        ret = GetEntryCycle(head1,meet1);         //求取相交点  
        ret = ret->next;  
        cur->next = NULL;                         //将链表复原  
    }  
    else if (meet1&&meet2)                        //如果两个链表都带环  
    {  
        endNode = GetEntryCycle(head1, meet1);    //找到环入口的前一个结点  
        cur = endNode->next;                      //保存环的入口  
        endNode->next =head2->next;               //将环变形  
        meet1 = GetCycleMeet(head1);              //获取变形之后这个环的相遇点  
        ret = GetEntryCycle(head1,meet1);         //获得交点  
        ret = ret->next;  
        endNode->next = cur;                      //复原链表  
    }  
    return ret;  
}