算法-链表-环形链表（链表求环）

迷南。 2023-07-24 08:43 156阅读 0赞

# 算法-链表-环形链表（链表求环） #

# 1 题目出处 #

https://leetcode-cn.com/problems/linked-list-cycle-ii/

# 2 题目描述 #

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

进阶：  
你是否可以不用额外空间解决此题？

# 3 题解 #

## 3.1 迭代+HashSet ##

### 3.1.1 解题思路 ###

set记录+遍历链表

### 3.1.2 代码 ###

public static ListNode detectCycle2(ListNode head) { 
        if (head == null){ 
            return null;
        }
        Set<ListNode> listNodeSet = new HashSet<>();
        ListNode ite = head;
        while(ite != null){ 
            if(listNodeSet.contains(ite)){ 
                return ite;
            }
            listNodeSet.add(ite);
            ite = ite.next;
        }
        return null;
    }

### 3.1.3 时间复杂度 ###

O(N)

### 3.1.4 空间复杂度 ###

O(N)

## 3.2 快慢指针 ##

### 3.2.1 解题思路 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]

1.  使用快慢指针，其中快指针步长为2，慢指针步长为1。  
    如果快指针走到null说明无环，返回null。
2.  如果相遇，则设为meet节点，且将路程拆分如下：
    
     *  a = head到环起点路程
     *  b = 环起点到meet节点的路程
     *  c = 从meet节点到环起点
3.  因为快指针路程为慢指针两倍，所以 2\*(a + b) = a + b + c + b，可得a == c  
    也就是说，`从head到环起点的路程`等于`从meet到环起点的路程`
4.  使用两个指针从这两个起点步长相同往后遍历，相遇时就是环起点

### 3.2.2 代码 ###

public ListNode detectCycle(ListNode head) { 
        if(null == head || head.next == null){ 
            return null;
        }
    
        ListNode fast = head;
        ListNode slow = head;
        ListNode meet = null;
        while(fast!=null){ 
            fast = fast.next;
            if(fast == null){ 
                // 无环
                return null;
            }
            fast = fast.next;
            slow = slow.next;
            if(fast == slow){ 
                meet  = fast;
                break;
            }
        }
    
        if(meet == null){ 
            // 未相遇，无环
            return null;
        }
    
        // slow从head开始，fast从meet开始，每次步长一致，相遇的地方就是入环首节点
        slow = head;
        while(slow != fast){ 
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

### 3.2.3 时间复杂度 ###

O(N)

### 3.2.4 空间复杂度 ###

O(1)

# 参考文档 #

林沐

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: /images/20230528/3240bd4b6f1248408fa631f27207c448.png