【LeetCode】环形链表II

阳光穿透心脏的1/2处 2023-07-04 03:29 11阅读 0赞

## 题目描述 ##

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。  
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。  
\*\*说明：\*\*不允许修改给定的链表。  
**示例1：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70]  
**示例2：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70 1]  
**示例3：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70 2]

## 解题思路 ##

可以分为两个部分。首先判断出该链表是否有环。其次，用相遇结点来找到环的入口。  
第一部分：设置快、慢两个指针，慢指针走一步，快指针走两步。如果链表中不存在环，快指针最终会走到尾部，此时返回NULL；若链表中存在环，快指针最终会追上慢指针，返回相遇结点。  
第二部分：设置meet指针指向根据第一部分找出的相遇结点，然后每次将meet指针和head指针往前移动一步，直到它们相遇，它们相遇的点就是环的入口，返回这个节点。

## 完整代码 ##

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
     //判断链表是否有环
    struct ListNode *hasCycle(struct ListNode *head) { 
        struct ListNode* fast = head;
        struct ListNode* slow = head;
        while(fast && fast->next)
        { 
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
            { 
                return fast;
            }
        }
        return NULL;
    }
    
    //找环的入口
    struct ListNode* detectCycle(struct ListNode* head){ 
        struct ListNode* meet = hasCycle(head);
        if(meet == NULL)
        { 
            return NULL;
        }
        while(1)
        { 
            if(meet == head)
            { 
                return meet;
            }
            meet = meet->next;
            head = head->next;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200207191915241.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200207191958761.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200207192030293.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg==,size_16,color_FFFFFF,t_70