141.环形链表 & 142.环形链表II

141.环形链表 & 142.环形链表II

141.环形链表

思路：快慢指针 or 哈希表

快慢指针代码：

1. class Solution {
2. public:
3.     bool hasCycle(ListNode *head) {
4.         if(head==nullptr||head->next==nullptr)
5.         return false;
6.         ListNode *fast=head->next; //不能设置成head，否则不进入while循环
7.         ListNode *slow=head;
8.         while(fast!=slow){
9.             //如果无环fast在slow前面，只需要判断fast
10.             if(fast->next!=nullptr&&fast->next->next!=nullptr){
11.                 fast=fast->next->next;
12.                 slow=slow->next;
13.             }else{  //无环
14.                 return false;
15.             }
16.         }
17.         return true;
18.     }
19. };

复制代码

哈希表代码：

1. class Solution {
2. public:
3.     ListNode *detectCycle(ListNode *head) {
4.         unordered_set<ListNode*> hash;
5.         ListNode* cur=head;
6.         while(cur!=nullptr){
7.             //哈希表中出现过
8.             if(hash.count(cur)){
9.                 return cur;
10.             }
11.             hash.insert(cur);
12.             cur=cur->next;
13.         }
14.         return nullptr;
15.     }
16. };

复制代码

142.环形链表II

思路：快慢指针+数学推导 or 哈希表

哈希表同前，数学推导见下图，

代码：

1. class Solution {
2. public:
3.     ListNode *detectCycle(ListNode *head) {
4.         ListNode *slow = head, *fast = head;
5.         while (fast != nullptr) {
6.             slow = slow->next;
7.             if (fast->next == nullptr) {
8.                 return nullptr;
9.             }
10.             fast = fast->next->next;
11.             if (fast == slow) {
12.                 ListNode *ptr = head;
13.                 while (ptr != slow) {
14.                     ptr = ptr->next;
15.                     slow = slow->next;
16.                 }
17.                 return ptr;
18.             }
19.         }
20.         return nullptr;
21.     }
22. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。