深圳做网站哪里好,现在去北京政策最新,东莞做网站企业,东莞电商页面设计公司前言 题目#xff1a; 142. 环形链表 II 文档#xff1a; 代码随想录——环形链表 II 编程语言#xff1a; C 解题状态#xff1a; 思路错误#xff0c;链表不允许被修改 思路
两步走#xff0c;第一步#xff0c;判断有没有环#xff0c;第二步#xff0c;判断入环口…前言 题目 142. 环形链表 II 文档 代码随想录——环形链表 II 编程语言 C 解题状态 思路错误链表不允许被修改 思路
两步走第一步判断有没有环第二步判断入环口在哪边。
代码
快慢指针法 第一步 定义两个指针一个快指针一个慢指针。快指针每次平移两个慢指针每次平移一个。如果两个指针可以相遇就代表有环。在一个环内快速的移动肯定会经过慢速的移动 第二步 在两个指针的相遇处令头节点和相遇节点相向而行两个指针必定会相遇并且相遇点就是环的入口。数学推理可见代码随想录讲解。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast head;ListNode* slow head;while (fast ! NULL fast - next ! NULL) {fast fast - next - next;slow slow - next;if (fast slow) {ListNode* index1 fast;ListNode* index2 head;while (index1 ! index2) {index1 index1 - next;index2 index2 - next;}return index1;}}return NULL;}
};时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
