LeetCode142 环形链表 II

前言

题目： 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(1)$