如何自己做收费的视频网站,比较专业的app开发公司,域名的正确书写格式,滁州新橙科技网站建设#x1f4f7; 江池俊#xff1a; 个人主页 #x1f525;个人专栏#xff1a; ✅数据结构探索 ✅LeetCode每日一道 #x1f305; 有航道的人#xff0c;再渺小也不会迷途。 LeetCode 160. 相交链表 思路#xff1a; 首先计算两个链表的长度#xff0c;然后判断两个链… 江池俊 个人主页 个人专栏 ✅数据结构探索 ✅LeetCode每日一道 有航道的人再渺小也不会迷途。 LeetCode 160. 相交链表 思路 首先计算两个链表的长度然后判断两个链表的尾节点是否相同。如果不同那么这两个链表就没有交集返回空如果相同那么就通过计算两个链表的长度差让长链表先走差距步然后两个链表一起走直到它们相遇。
具体步骤如下 初始化两个指针 cur1 和 cur2 分别指向 headA 和 headB即两个链表的头节点。同时初始化两个变量 lenA 和 lenB 分别用来计算两个链表的长度。通过循环计算 lenA 和 lenB这里的循环是计算链表的长度cur1 和 cur2 分别最后会指向链表的尾节点。判断 cur1 和 cur2 是否相等如果不同说明两个链表没有交集返回空。如果 cur1 和 cur2 相等说明两个链表有交集。这时需要确定哪个链表长哪个链表短。长链表先走差距步使两个链表的尾节点对齐。通过循环让长链表先走差距步这里的差距 n 是两个链表长度的差。然后两个链表一起走直到它们相遇。当 longList 和 shortList 相遇时返回相遇节点。 时间复杂度O(mn) 空间复杂度O(1)
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *cur1 headA;struct ListNode *cur2 headB;int lenA 1,lenB 1;while(cur1-next)//计算第一个链表的长度{cur1 cur1-next;lenA;}while(cur2-next)//计算第二个链表的长度{cur2 cur2-next;lenB;}if(cur1!cur2)//判断两个链表的尾节点是否相同{return NULL;}int n abs(lenA-lenB);//得到差距步struct ListNode *longList headA;struct ListNode *shortList headB;if(lenAlenB){longList headB;shortList headA;}while(n--)//先走差距步{longList longList-next;}//一起走while(longList!shortList){longList longList-next;shortList shortList-next;}return longList;
}✅今日分享就到这里了如果大家有什么疑问可以在评论区与我讨论或者直接私信我
