网站建设课程教学计划,网页设计师培训多少钱,微商软件,婚庆网站建设论文【Leedcode】数据结构中链表必备的面试题#xff08;第四期#xff09; 文章目录【Leedcode】数据结构中链表必备的面试题#xff08;第四期#xff09;1.题目2.思路图解(1)思路一(2)思路二3.源代码总结1.题目 相交链表#xff1a; 如下#xff08;示例#xff09;…【Leedcode】数据结构中链表必备的面试题第四期 文章目录【Leedcode】数据结构中链表必备的面试题第四期1.题目2.思路图解(1)思路一(2)思路二3.源代码总结1.题目 相交链表 如下示例 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
图示两个链表在节点 c1 开始相交题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。1.判断两个链表是否相交 2.如果相交求交点 2.思路图解
(1)思路一
暴力求解-穷举法。依次取A链表中的每个节点跟B链表中的所有结点比较。 如果有相同的结点就是相交第一个相同的交点就是公共结点。这样做的时间复杂度为O(N^2) 那么我们如何把时间复杂度优化到O(N) (2)思路二
1.尾结点相同就是相交否则就不相交 2.求交点长的链表先走长度差步再同时走第一个相同的结点就是交点具体如下图 再这里要注意可以用lenA和lenB去算两个链表的长度方便求交点位置如下图 3.源代码 代码如下示例 struct ListNode
{int val;struct ListNode *next;
};
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* pheadA headA;struct ListNode* pheadB headB;//先判断是否为环形结构int lenA 1;while(pheadA - next){lenA;pheadA pheadA - next;}int lenB 1;while(pheadB - next){lenB;pheadB pheadB - next;}if(pheadA ! pheadB){return NULL;}int sub abs(lenA - lenB);struct ListNode* longlist headA;struct ListNode* shortlist headB;if(lenA lenB){longlist headB;shortlist headA;}//长的先走sub步while(sub--){longlist longlist - next;}//俩个开始一起走while(longlist ! shortlist){longlist longlist - next;shortlist shortlist - next;}return longlist;
}总结
以上就是今天要讲的内容本文介绍数据结构中链表必备的面试题第四期 如果我的博客对你有所帮助记得三连支持一下感谢大家的支持
