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

141.环形链表¹

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

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

示例 1：

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

示例 2：

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

示例 3：

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

解法一：枚举法

• 思路：用一个表保存所有结点，若结点已经在表中，则有环
  • 这里的表用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²

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 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
解释：链表中没有环。

解法一：双指针（快慢）

• 思路：这其实是一个规律，快慢指针相遇后，快指针从头再与慢相遇处即环始点
• 复杂度
  • 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;
}