题目:160. 相交链表
给你两个单链表的头节点
headA
和headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回null
思路一(暴力求解):
A链表的每个节点依次跟B链表中节点进行比较,如果有相等就是相交,第一个相等就是交点
接下来我们看一下思路一的时间复杂度吧~
因为我们这里不知道这两个链表之间的大小关系,
所以时间复杂度可以是O(N^2)或者O(N*M)
思路二:
1.先找尾节点,尾节点的地址相同就相交,不相同直接返回NULL
2.接下来要处理的就是判断相交链表的第一个节点,我们先计算两个链表的长度,让长的链表先走完长度差,再同时找交点,第一个地址相同的就是交点
接下来我们看一下思路二的时间复杂度
这里算了一下是3N,所以时间复杂度就应该是O(N),显然要优于思路一
所以接下来我们来实现一下思路二~
首先第一步:先找尾节点,尾节点的地址相同就相交,不相同直接返回NULL
代码如下:
struct ListNode* curA = headA;struct ListNode* curB = headB;while(curA->next){curA = curA->next;}while(curB->next) {curB = curB->next;}if(curA!=curB) return NULL;//尾节点不相等,说明不相交,直接返回NULL
接下来第二步:
a.分别算出两个链表的长度,进而算出二者的长度差值
b.让长的链表先走完长度差
c. 两个链表同时走,直到遇到相同的节点
代码如下:
curA = headA;curB = headB;int lenA = 0, lenB = 0;//分别算出两个链表的长度while(curA){lenA++;curA = curA->next;}while(curB) {lenB++;curB = curB->next;}int len = abs(lenA-lenB);//len为二者的长度差struct ListNode* longList = headA;struct ListNode* shortList = headB;if(lenB>lenA){longList = headB;shortList = headA;}//让长的链表先走完长度差while(len!=0){longList = longList->next;len--;}//两个链表同时走,直到遇到相同的节点while(longList != shortList){longList = longList->next;shortList = shortList->next;}return longList;
将上面两步的代码结合起来,这道题就过了
当然,我们也可以将这个代码写得更简略一些:比如将计算长度的代码融入第一步的遍历
这里因为要逻辑更清晰一些才将它们分开的,不过这些也都是小问题而已啦
好啦,到此为止,今天的相交链表问题就结束啦,如果文中分析,题解代码有不足的地方欢迎大家在评论区讨论和指正
让我们在接下来的时间里一起学习,一起进步吧~