每日一题---OJ题: 相交链表

片头

嗨! 小伙伴们,大家好! 今天我们来一起学习这道OJ题---相交链表,准备好了吗? Ready Go! ! !

emmm,看这道题好像不怎么难,我们一起画图分析分析

上图中,A链表有5个结点,分别为 a1,a2,c1,c2,c3 ; B链表有6个结点,分别为 b1,b2,b3,c1,c2,c3 ; A链表和B链表在c1结点相交

怎么做这道题呢? 第一种思路就是暴力穷举,也是一种比较容易想到的办法

思路一: 让A链表的每一个结点依次跟B链表中的结点进行比较,如果有相等就是相交,第一个相等就是交点。

代码如下：

 typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
        ListNode* pA = headA;   //定义一个指向A链表的指针
        ListNode* pB = headB;   //定义一个指向B链表的指针

        //让A链表的每一个结点依次和B链表中的结点进行比较
        for(pA = headA; pA != NULL; pA = pA->next){
            for(pB = headB; pB != NULL; pB = pB->next){
                if(pA == pB){   //如果有相等就是相交
                    return pA;  //第一个相等就是交点
                }
            }
        }
        return NULL;            //如果没有相交,返回NULL
}

我们把代码放到leetcode上面,显示通过

那还没有另外一种思路呢? 肯定有,且听我慢慢道来~

思路二: 1. 判断是否相交先找尾结点,尾结点的地址相同就相交; 2.找交点长的链表先走长度差,再同时走找交点(第一个地址相同的就是交点)。

判断是否相交的代码如下：(因为后面我们需要知道长度差,因此在寻找尾结点的同时就计算链表的长度,效率更高)

        ListNode* pA = headA;       //定义pA指针,指向A链表的头结点
        ListNode* pB = headB;       //定义pB指针,指向B链表的头结点

        int lenA = 0;               //A链表的长度
        while(pA->next != NULL)     //寻找A链表的尾结点
        {
            pA = pA->next;          //如果不是尾结点,pA往后走一步
            lenA++;                 //lenA的长度自增一次
        }
        lenA = lenA+1;              //别忘了加上尾结点

        int lenB = 0;                //B链表的长度
        while(pB->next != NULL)      //寻找B链表的尾结点
        {
            pB = pB->next;           //如果不是尾结点,pB往后走一步
            lenB++;                  //lenA的长度自增一次
        }
        lenB = lenB+1;               //别忘了加上尾结点

        if(pA != pB){                //如果尾结点不相同,说明两个链表不会相交
            return NULL;             //返回NULL
        }

接下来就是尾结点相同,说明两个链表相交,我们一起来找交点

部分代码如下:

 //尾结点相同,说明两个链表相交,我们一起来找交点
        int gap = abs(lenA-lenB);   //abs()函数用来求绝对值

        //假设A链表的长度比B链表短
        //用变量shortList定义A链表,变量longList定义B链表
        ListNode* shortList = headA;
        ListNode* longList = headB;

        //如果A链表的长度比B链表长
        if(lenA > lenB)
        {
            longList = headA;  //变量longList定义A链表
            shortList = headB;//用变量shortList定义B链表,
        }

        //长的链表先走长度差
        while(gap--){
            longList = longList->next;
        }
        //再同时走找交点
        while(longList != shortList){
            longList = longList->next;
            shortList = shortList->next;
        }
        //找到交点了,返回结点
        return longList;

OK,这道题被我们解决了,整体代码如下:

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
        ListNode* pA = headA;       //定义pA指针,指向A链表的头结点
        ListNode* pB = headB;       //定义pB指针,指向B链表的头结点

        int lenA = 0;               //A链表的长度
        while(pA->next != NULL)     //寻找A链表的尾结点
        {
            pA = pA->next;          //如果不是尾结点,pA往后走一步
            lenA++;                 //lenA的长度自增一次
        }
        lenA = lenA+1;              //别忘了加上尾结点

        int lenB = 0;                //B链表的长度
        while(pB->next != NULL)      //寻找B链表的尾结点
        {
            pB = pB->next;           //如果不是尾结点,pB往后走一步
            lenB++;                  //lenA的长度自增一次
        }
        lenB = lenB+1;               //别忘了加上尾结点

        if(pA != pB){                //如果尾结点不相同,说明两个链表不会相交
            return NULL;             //返回NULL
        }

        //尾结点相同,说明两个链表相交,我们一起来找交点
        int gap = abs(lenA-lenB);   //abs()函数用来求绝对值

        //假设A链表的长度比B链表短
        //用变量shortList定义A链表,变量longList定义B链表
        ListNode* shortList = headA;
        ListNode* longList = headB;

        //如果A链表的长度比B链表长
        if(lenA > lenB)
        {
            longList = headA;  //变量longList定义A链表
            shortList = headB;//用变量shortList定义B链表,
        }

        //长的链表先走长度差
        while(gap--){
            longList = longList->next;
        }
        //再同时走找交点
        while(longList != shortList){
            longList = longList->next;
            shortList = shortList->next;
        }
        //找到交点了,返回结点
        return longList;
}

哈哈哈,代码量看似很多,但是里面的逻辑一点也不复杂,只要认真分析,一定能克服难关!