leetcode之hot100---142环形链表II（C++）

embedded/2024/12/26 19:45:24/

思路一：哈希表

参考环形链表的思路一，当在哈希表中找到第一个表外待入表的节点，说明链表存在环，且该节点为入环的第一个节点

class Solution {
public:ListNode *detectCycle(ListNode *head) {unordered_set<ListNode *> visited;while (head != nullptr) {if (visited.count(head)) {return head;}visited.insert(head);head = head->next;}return nullptr;}
};

时间复杂度：O(N)
空间复杂度：O(N)

思路二：快慢指针

与前述环形链表不同的是，判断是否存在环中的快慢指针最终可能不会返回入环点

图示解释：

初始时，

slow: 3

fast: 3

第一次移动：

slow: 3->2

fast: 3->0

第二次移动：

slow: 3->2->0

fast: 3->0->2

第三次移动：

slow: 3->2->0->-4

fast: 3->0->2->-4

由上图示例可知，slow最终返回并不是入环的第一个节点，因此需要想办法让代码返回入环的第一个节点

快慢指针关系：

如果将环外的距离用a来表示，入环的第一个节点与两指针相遇的距离用b来表示，环中除b外的距离用c表示，那么可以得到两指针移动的距离：

$s(fast) = a + n * (b + c) + b$

$s(slow) = a + b$

由上图总结可得：

每次slow移动一步，fast每次移动两步，也就是说fast移动的距离是slow移动的两倍，用s(slow)和s(fast)分别代表两个指针移动的距离，那么两者的关系可以用数学公式可以这样表示：

$s(fast) = 2 * s(slow)$

整理上述三个式子可得：

$2 * ( a +b ) = a + n * (b + c) + b$

也就是：

$a = c + (n - 1) * (b +c)$

因此，可以额外使用一个指针ptr，使其最开始指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇，也就是说，ptr走a个距离后会和走c + (n - 1) * (b +c)距离的slow在入环的第一个节点处相遇

/*** 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) {if(head == nullptr || head->next == nullptr){return nullptr;}ListNode* slow = head;ListNode* fast = head;while(fast != nullptr){slow = slow->next;if(fast->next == nullptr){return nullptr;}fast = fast->next->next;if(slow == fast){ListNode* ptr = head;while(ptr != slow){ptr = ptr->next;slow = slow->next;}return ptr;}}return nullptr;}
};