力扣-142题环形链表II（C++）- 哈希法、快慢指针法

墨蓝 2022-09-05 15:52 171阅读 0赞

题目链接：[https://leetcode-cn.com/problems/linked-list-cycle-ii/][https_leetcode-cn.com_problems_linked-list-cycle-ii]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 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) {
        
            unordered_set<ListNode*> hs;
    
            while(head!=NULL){
        
                if(hs.count(head)!=0) {
        return head;}
                hs.insert(head);
                head=head->next;
            }
    
            return NULL;
        }
    };

解法二：

/**
     * 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,*slow=head;
    
            while(fast!=NULL&&fast->next!=NULL){
        
                slow=slow->next;
                fast=fast->next->next;
                
                //快慢指针相遇，说明存在环。
                //此时从head和相遇点，同时查找直至相遇
                if(fast==slow){
        
                    ListNode* index1=fast;//此处fast和slow都可以，主要是另一个从头重新开始
                    ListNode* index2=head;
    
                    while(index1!=index2){
        
                        index1=index1->next;
                        index2=index2->next;
                    }
    
                    return index1;//返回环的入口 此处index1和index2都可以
                }
            }
    
            return NULL;
        }
    };

[https_leetcode-cn.com_problems_linked-list-cycle-ii]: https://leetcode-cn.com/problems/linked-list-cycle-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/a409526f093c41a8adf08cfd38a54399.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]: /images/20220829/1f7feb46b7dc4472804baad48b87a30d.png