邯郸建网站公司,网站模板 百科,全面的苏州网站建设,成功的o2o平台有哪些题目 给一个长度为n链表#xff0c;若其中包含环#xff0c;请找出该链表的环的入口结点#xff0c;否则#xff0c;返回null。
数据范围#xff1a;1结点值10000
要求#xff1a;空间复杂度O(1)#xff0c;时间复杂度O(n)
例如#xff0c;输入{1,2},{3,4,5…题目 给一个长度为n链表若其中包含环请找出该链表的环的入口结点否则返回null。
数据范围1结点值10000
要求空间复杂度O(1)时间复杂度O(n)
例如输入{1,2},{3,4,5}时对应的环形链表如下图所示 可以看到环的入口结点的结点值为3所以返回结点值为3的结点。
输入描述
输入分为2段第一段是入环前的链表部分第二段是链表环的部分后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表。
返回值描述
返回链表的环的入口结点即可我们后台程序会打印这个结点对应的结点值若没有则返回对应编程语言的空结点即可。
示例1
输入
{1,2},{3,4,5}
返回值
3
说明
返回环形链表入口结点我们后台程序会打印该环形链表入口结点对应的结点值即3 示例2
输入
{1},{}
返回值
null
说明
没有环返回对应编程语言的空结点后台程序会打印null示例3
输入
{},{2}
返回值
2
说明
环的部分只有一个结点所以返回该环形链表入口结点后台程序打印该结点对应的结点值即2思路 首先题目中给的链表并不一定是有环的所以需要先判断链表是否有环。可以在通过快慢指针的方式来判断如果有环则可以计算出环节点的个数。
然后定义两个指针初始化指向头节点第一个指针先前进环节点个数之后两个节点同时前进到节点值相等的节点就是环的入口节点。
本题还可以使用哈希表unordered_set来记录经过的节点来解决但是这个方法的空间复杂度时O(n)。
另外我的解法写的比较复杂主要是为了理顺思路。使用快慢指针可以用更简洁的代码解决。
解答代码 /*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead) {if (pHead nullptr || pHead-next nullptr) {return nullptr;}// 获取到环节点的个数int loop_node_num GetLoopNodeNum(pHead);if (loop_node_num 0) {// 链表中没有环return nullptr;}ListNode* pNode1 pHead;ListNode* pNode2 pHead;// 第一个节点先前进loop_node_num步for (int i 0; i loop_node_num; i) {pNode1 pNode1-next;}// 两个节点同时前进while (pNode1-val ! pNode2-val) {pNode1 pNode1-next;pNode2 pNode2-next;}// 相等的点就是环的入口return pNode1; }int GetLoopNodeNum(ListNode* pHead) {int loop_node_num 0;// 定义快慢指针ListNode* fast pHead-next;ListNode* slow pHead;// 判断是否有环bool is_loop false;while (fast ! nullptr) {if (fast-val slow-val) {is_loop true;break;} else {if (fast-next ! nullptr) {fast fast-next-next;slow slow-next;} else {break;}}}// 有环则步进慢指针计算环的节点数if (is_loop) {int val slow-val;loop_node_num 1; // 加上自身while (val ! slow-next-val) {loop_node_num;slow slow-next;}}return loop_node_num;}
};
