外文网站制作,地推的60种方法,谷歌排名算法,免费做一个自己app文章目录 1. 题目介绍2. 思路1#xff1a;暴力求解算法思想代码实现 3. 思路2#xff1a;快慢指针算法思想代码实现 1. 题目介绍
链接: link 给你两个单链表的头节点 headA 和 headB #xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点… 文章目录 1. 题目介绍2. 思路1暴力求解算法思想代码实现 3. 思路2快慢指针算法思想代码实现 1. 题目介绍
链接: link 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
2. 思路1暴力求解
算法思想
首先第一种思路就是暴力求解这可能是我们最容易想到的 让A链表的每个结点依次与B中所有结点逐个比较拿B的跟A比也是一样当然这里要注意比较的时候应该比较结点的地址而不应该比较结点的值。结点的值一样并不能证明它们相交。 这种方法思想很简单但是效率不好这样的话时间复杂度就是ON^2 代码实现
代码也很简单可以给大家写一下 也可以通过。 //暴力求解让A链表的每个结点依次与B中所有结点逐个比较。ON^2
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{struct ListNode* curA headA;struct ListNode* curB headB;while (curA){curBheadB;while (curB){if (curA curB)return curA;curB curB-next;}curA curA-next;}return NULL;
}但是上面的算法效率不是很好我们能不能优化一下呢
3. 思路2快慢指针
算法思想
大家思考一个问题 上面我们暴力比对结点的地址来寻找链表的交点。 但是为什么要拿A链表的每个结点依次与B中所有结点逐个比较呢 为什么不能同步的遍历两个链表比较对应的结点呢 如果同步遍历话就是ON了 不能直接这样因为两个链表的长度可能是不一样的。 比如像这样 如果我们同步的遍历去比对显然是不行的不能得到正确的结果。 那不能直接同步遍历两个链表的去比较我们能不能想个办法让他们可以同步遍历去比较呢 我们来分析一下。 如果两个链表相交但是长度不相等那么不相等的部分一定是在交点之前的。 因为相交之后它们后面的结点都是一样的嘛。 那上面我们分析了就是因为两个链表的长度可能不一样所以不能同步遍历去比较。 那我们能不能把他们变成一样长呢 我们可以这样做 我们可以同步遍历去比较。 但是如果长度不相等我们要先让较长的那个链表的遍历指针先走长度的差值步 此时我们看到是不是就可以让curA和curB同时往后走比较对应的结点了。 这样如果它们有交点的话就一定会出现curAcurB此时这两个指针指向的结点就是第一个交点返回curA或curB都可。 如果没有交点那就一直往后走curA不会和curB相等遍历结束curA和curB都走到空返回curA或curB都可。当然待会大家看我们的代码不相交的话我们在求长度差值的时候其实就能判断出来了 所以 我们可以先遍历一遍两个链表求出它们的长度判断出谁长谁短并计算出长度的差值。 然后让长的链表先走差值步再同步往后走比较对应结点找交点。 代码实现
理清了思路我们来写一下代码 提交一下 过啦 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curAheadA;struct ListNode *curBheadB;int lenA0;int lenB0;//找尾先判断是否相交不相交直接返回NULL相交再找while(curA-next){lenA;curAcurA-next;}//计算准确长度应该这样写while(curA)//这样while(curA-next)比实际长度小1但是两个都小1不影响差值//而这样写循环结束cur就是尾可直接判断是否相交while(curB-next){lenB;curBcurB-next;}//尾不相等则不相交if(curA!curB)return NULL;//计算差值int gapabs(lenA-lenB);//找出长的那一个struct ListNode *longlistheadA;struct ListNode *shortlistheadB;if(lenBlenA){longlistheadB;shortlistheadA;}//长表先走差值步while(gap--){longlistlonglist-next;}//再一起走比较两个链表的当前结点是否相同//第一个相同的就是第一个交点while(longlist!shortlist){longlistlonglist-next;shortlistshortlist-next;}return longlist;
}
