每日一题---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;
}

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