LeetCode题目之腾讯精选练习（50题）：环形链表 II

阳光穿透心脏的1/2处 2024-04-19 08:04 82阅读 0赞

# 题目 #

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

**说明** ：不允许修改给定的链表。

**示例 1** :

输入：head = [3,2,0,-4], pos = 1
    输出：tail connects to node index 1
    解释：链表中有一个环，其尾部连接到第二个节点。

![在这里插入图片描述][20190915153856690.png]  
**示例 2** :

输入：head = [1,2], pos = 0
    输出：tail connects to node index 0
    解释：链表中有一个环，其尾部连接到第一个节点。

![在这里插入图片描述][20190915153902282.png]  
**示例 3** :

输入：head = [1], pos = -1
    输出：no cycle
    解释：链表中没有环。

![在这里插入图片描述][20190915153912217.png]

## 算法实现 ##

public ListNode DetectCycle(ListNode head)//利用哈希表
    {
        
        var a = new HashSet<ListNode>();
        while (head != null)
        {
        
            if (a.Contains(head))
                return head;
            else
                a.Add(head);
            head = head.next;
        }
        return null;
    }
    public ListNode DetectCycle(ListNode head)//快慢指针
    {
        
        if (head == null || head.next == null)
        {
        
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (true)
        {
        
            if (fast == null || fast.next == null)
            {
        
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast)
                break;
        }
        fast = head;
        while (fast != slow)
        {
        
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

## 执行结果 ##

**执行结果** : 通过  
**执行用时** : 132 ms, 在所有 C\# 提交中击败了100.00%的用户  
**内存消耗** : 25.9 MB, 在所有 C\# 提交中击败了5.00%的用户

**利用哈希表**  
![利用哈希表][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]  
**快慢指针**  
![快慢指针][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70 1]

## 小的总结 ##

本次题目对上次的环形链表的两种方法进行稍加改进即可。

[20190915153856690.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/3ccc642f321e40f08b7c89d16cff3f95.png
[20190915153902282.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/62c0ab24b5c64af1a44be370b4aef9df.png
[20190915153912217.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/632d53db2fbe48f08703d40731b19b08.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/60c8b0c8ed354fc5a572cc219e2db4e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5fd29d712acb44b7b54561a32aab576c.png