【数据结构】链表：LeetCode题（二）141.环形链表I，142.环形链表II

布满荆棘的人生 2022-12-09 14:58 122阅读 0赞

## [141.环形链表¹][141.] ##

给定一个链表，判断链表中是否有环。

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

**示例 1：**

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

![img][]

**示例 2：**

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

![img][img 1]

**示例 3：**

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

![img][img 2]

### 解法一：枚举法 ###

*  思路：用一个表保存所有结点，若结点已经在表中，则有环
    
     *  这里的表用HashSet最好，因为 set 的 contains 方法与 add 方法都是基于hash表，复杂度 O(1）–> 5ms
     *  若用ArrayList，则 contains 方法的复杂度是 O(n）–> 372ms
 *  复杂度
    
     *  Time：O（n）
     *  Space：O（n），链表中的每个节点都要放到容器中

public boolean hasCycle(ListNode head) {
        
            if (head == null || head.next == null) return false;
    
            ListNode node = head;
        	// 这里太合适用set了
            Set<ListNode> set = new HashSet<>();
            while(node.next != null) {
        
                if (set.contains(node)) 
                    return true;
                    set.add(node);
                    node = node.next;
            }
            return false;
    }

### 解法二：双指针（快慢） ###

*  思路：如果有环，走的快（一次两步）的指针一定能追上走的慢的指针（一次一步）
 *  复杂度
    
     *  Time：O（n）
     *  Space：O（1）

public boolean hasCycle(ListNode head) {
        
            if (head == null || head.next == null) return false;
    
            ListNode qn = head,sn = head; // quickNode，slowNode
        	// 关键是这个判断条件
        	// qn != null 保证了 qn.next 不会出现空指针异常；
        	// qn.next != null 保证了 qn.next.next 不会出现空指针异常；
            while (qn != null && qn.next != null) {
         
                sn = sn.next;
                qn = qn.next.next;
                if (sn == qn) {
        
                    return true;
                }
            }
            return false;
    }

--------------------

## [142.环形链表 II²][142._ II] ##

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

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

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

**示例 1：**

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

![img][]

**示例 2：**

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

![img][img 1]

**示例 3：**

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

![img][img 2]

### 解法一：双指针（快慢） ###

*  思路：这其实是一个规律，**快慢指针相遇后，快指针从头再与慢相遇处即环始点**
 *  复杂度
    
     *  Time：O（n）
     *  Space：O（1）

public ListNode detectCycle(ListNode head) {
        
            ListNode fast = head;
            ListNode slow = head;
            // 让快慢指针相遇
            while (true) {
        
                // 无环判断
                // 注意：这里不能放到循环条件，假设，那么退出循环那部分如何操作？
                if (fast == null || fast.next == null) {
        
                    return null;
                }
                fast = fast.next.next;
                slow = slow.next;
                // 定位到两指针相遇处
                if (slow == fast) {
        
                    break;
                }
            }
        	// 将快指针从头开始，慢指针还在相遇处
            fast = head;
        	// 两指针再次相遇位置就是环始点
            while (fast != slow) {
        
                fast = fast.next;
                slow = slow.next;
            }
    
            return fast;
    }

[141.]: https://leetcode-cn.com/problems/linked-list-cycle/
[img]: /images/20221123/65ca00f9d78647f4bff04c810a859375.png
[img 1]: /images/20221123/d70a6225f47e43a383a52aea18140fbb.png
[img 2]: /images/20221123/ad539a3d0b88440692acd7b24e5affdd.png
[142._ II]: https://leetcode-cn.com/problems/linked-list-cycle-ii/