财务软件费用计入什么科目,网站优化软件费用,pr软件,织梦网站空间如何清理文章目录 #x1f4a1;题目分析#x1f4a1;解题思路#x1f6a9;步骤一#xff1a;找尾节点#x1f6a9;步骤二#xff1a;判断尾节点是否相等#x1f6a9;步骤三#xff1a;找交点#x1f344;思路1#x1f344;思路2 #x1f514;接口源码 题目链接#x1f449;… 文章目录 题目分析解题思路步骤一找尾节点步骤二判断尾节点是否相等步骤三找交点思路1思路2 接口源码 题目链接
LeetCode 160.相交链表 题目分析 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 解题思路
步骤一找尾节点 struct ListNode* tailA headA;struct ListNode* tailB headB;int lenA 1,lenB 1;while(tailA){tailA tailA-next;lenA;}while(tailB){tailB tailB-next;lenB;}步骤二判断尾节点是否相等 判断尾节点是否相等如果尾节点相等就是相交 if (tailA ! tailB)
{return NULL;
}步骤三找交点
思路1 A链表所有节点跟B链表都比较一遍相等的那个就是交点 这种暴力求解法解决这道题是没问题的。但是这种解法时间复杂度为 O(N^2) / O(N*M)要求优化到 O(N)所以我们不采用这种暴力解法建议使用下一种解法 思路2 分别定义两个链表的长度 lenA 和 lenB长的先走abs(lenA - lenB)步差距步然后再同时走第一个相等的就是相交节点 //长的先走差距步int gap abs(lenA - lenB); //abs函数是对整数进行取绝对值struct ListNode* longList headA;struct ListNode* shortList headB;if(lenA lenB){longList headB;shortList headA;}while(gap--){longList longList-next;}while(longList ! shortList){longList longList-next;shortList shortList-next;}图解 此方法整体时间复杂度为O(MN) / O(N)空间复杂度为O(1) 接口源码
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* tailA headA;struct ListNode* tailB headB;int lenA 1,lenB 1;while(tailA){tailA tailA-next;lenA;}while(tailB){tailB tailB-next;lenB;}//判断最后一个节点是否相等是否相交if(tailA ! tailB){return NULL;}//长的先走差距步int gap abs(lenA - lenB);struct ListNode* longList headA;struct ListNode* shortList headB;if(lenA lenB){longList headB;shortList headA;}while(gap--){longList longList-next;}//一一对应比较判断重叠节点(因为前面已经经过是否相交的判断所以执行至此必定是相交的)while(longList ! shortList){longList longList-next;shortList shortList-next;}//二者相等任意一一个都是相交起始点return longList;
}希望烙铁们能够理解欧 总结 以上就是本题讲解的全部内容啦 本文章所在【C/C刷题系列】专栏感兴趣的烙铁可以订阅本专栏哦 前途很远也很暗但是不要怕不怕的人面前才有路。 小的会继续学习继续努力带来更好的作品 创作写文不易还多请各位大佬uu们多多支持哦
