php智能建站系统,wordpress如何去掉显示文章的分类,wordpress用户名钩子,亚马逊网上商城是正品吗题目描述
给你两个单链表的头节点 headA和headB#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点#xff0c;返回 null。图示两个链表在节点 c1 开始相交#xff1a; 题目数据保证整个链式结构中不存在环。注意#xff0c;函数返回结果后请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null。图示两个链表在节点 c1 开始相交 题目数据保证整个链式结构中不存在环。注意函数返回结果后链表必须保持其原始结构 。
解题思路
暴力求解
在A链表中遍历每一个结点去B链表中依次找一遍但是这种方法的时间复杂度为O(N^2)因此这种方法想必不太好就不写代码实现了。
优雅解法
我们可能会这样想如果在交点前同样距离远的位置同时开始遍历两个链表那么在接下来的遍历过程中肯定会遍历到同一个结点当第一次遍历到同一个结点时那么这个结点就必然是交点。那么问题来了我们刚才的假设是在交点前同样距离远的位置同时开始遍历两个链表那么怎么才能做到这样呢这两个链表的长度很可能是不一样的。我们这样想分别遍历A、B这两个链表同时计算这两个链表的长度如果最终遍历到同一个结点那么这两个链表必然相交因此我们也可以计算出这两个链表长度的差值假设为dif。得到的这个差值很关键我们让较长的链表先开始走dif步然后两个链表再同时继续遍历当遍历到同一个结点时这个结点就是交点。
实现代码如下
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* curAheadA;struct ListNode* curBheadB;int sizeA1;int sizeB1;while(curA-next){curAcurA-next;sizeA;}while(curB-next){curBcurB-next;sizeB;}//判断相交if(curA ! curB)return NULL;int difabs(sizeA-sizeB);curAheadA;curBheadB;//长的先走dif步if(sizeA sizeB){while(dif--){curAcurA-next;}}else{while(dif--){curBcurB-next;}}//一起走while(curA ! curB){curAcurA-next;curBcurB-next;}return curA;
}
