LeetCode[142] 环形链表 II

哈希表匹配法

1. set存储遍历过的节点
2. 每次遍历查询set中是否有该节点
   • 有，则代表该节点为环的起点
   • 无，则插入set中，继续遍历链表

/*** 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) {unordered_set<ListNode*> myset; // 存储遍历过的节点while(head) // head为空时代表链表内没有环{if(myset.find(head)!=myset.end()) // 如果节点已经被遍历过，则为环的起点return head;myset.insert(head);head = head->next;}return nullptr;}
};

快慢指针

/*** 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* 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;}
};