8.16 哈希表中等 142 Linked List Cycle II review 141 Linked List Cycle

142 Linked List Cycle II

/*** 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) {//给一个链表的头头，返回循环的开始结点 如果没有循环返回null//判断有环的情况//环的位置判断，//哈希表使用--->快速查找unordered_set<ListNode*> nodeSet;ListNode *p = head;//尾指针while(p){if(nodeSet.find(p) == nodeSet.end()){//没找到nodeSet.insert(p);}else{return p;}p = p->next;}return nullptr;}
};

空间复杂度为O(1)

/*** 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) {//判断有环的情况-->同一个结点反复出现-->结点之间做比较-->双指针//环的位置判断-->pre比p先一步进入环中所以pre应该一直==p->next，此时pre直接一个绕后但他还是p->next//**怎么判断两个指针能够相撞呢**，一个跑的快一个跑得慢直至慢的被快的套圈,但不能保证套圈位置是在环的开头--->快慢指针//**怎么保证返回的结点是环的第一个结点**？-->计算if (!head || !head->next) return nullptr;ListNode *fast = head;ListNode *slow  = head;while(fast&&fast->next){slow = slow->next;fast = fast->next->next;if(fast == slow){// 将其中一个指针移到链表头部ListNode *p = head;// 两个指针同时向前移动while (p != slow) {p = p->next;slow = slow->next;}// 返回环的起始节点return p;}}return nullptr;}
};

review 8.8 141 Linked List Cycle

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {//快慢指针if(!head || !head->next) return false;ListNode *fast = head;ListNode *slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(fast == slow){return true;}}return false;}
};