算法 1.5 链表 + 快慢指针：环形链表【leetcode 1

题目描述

给定一个链表，判断链表中是否有环，存在环返回 true，否则返回 false

• 连续跟踪 next 指针再次到达某个节点，则链表中有环
• 你能用 O(1)（即，常量）内存解决此问题吗？

提示：
链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为环开始节点的索引，若 pos = -1，则没有环
pos 为 -1 或者链表中的一个 有效索引
pos 不作为参数进行传递，仅仅是为了标识链表的实际情况

注意：pos 只是帮助理解测试用例，并不是真正的输入值

数据结构

• 数组、指针变量

算法思维

• 遍历、双指针、快慢指针、追击

解题要点

• 链表的特点
• 快慢指针的思想以及使用
• 模型的应用：涉及"环"的问题 --> 追击问题 --> 快慢指针

---

解题步骤

一. Comprehend 理解题意

可以理解为"重复访问"问题，检测链表的某节点能否二次到达

• 需要一个容器记录已经访问过的节点
• 每次访问到新的节点，都与容器中的记录进行匹配，若相同则存在环
• 若匹配之后没有相同节点，则存入容器，继续访问新的节点
• 直到访问节点的next指针返回null，或者当前节点与容器的某个记录相同，操作结束

也可以理解为“追击”问题，如果存在环，跑得快的一定能追上跑得慢的

• 就像一快一慢两个运动员，如果在直道赛跑，不存在追击问题；
  如果是在环道赛跑，快的绕了一圈肯定可以追上慢的
• 定义快慢两个运动员，指向链表的第一、第二个节点：slow = head; fast = head.next;
• 快运动员的步长为2，慢的为1，即fast每次移动两个节点，slow每次移动一个节点
• 若最终 fast == slow ，说明存在环；若 fast == null || fast.next == null，操作结束

二. Choose 选择数据结构与算法

解题方法

• 解法一：二次到达法
• 解法二：追击问题法

解法一：二次到达法

数据结构：数组（或者：链表、栈、队列）
算法思维：遍历

解法二：追击问题法

数据结构：指针变量 x 2
算法思维：遍历、双指针（快慢指针）

三. Code 编码实现基本解法

解法一：二次到达法 -- 思路分析

1. 定义数组记录已访问节点：new ListNode[10000];
2. 遍历链表的每个节点，并与容器中已存放的节点依次比较：
   • 相同则方法结束，返回 true
   • 不同则存入最新位置，继续遍历下个节点
3. 若 next 指针为 null，则方法结束，返回 false

边界问题

• 数组越界：
  链表最多有一万个节点，容器不会越界；
  与容器中节点进行比对，正向遍历容器，元素为 null 时终止，后续都是未使用的空间

细节问题

• 遍历链表，通过 head=head.next 进行迭代
  当且仅当此节点与容器某个节点相同时返回 true，其它情况都返回 false
  比较相等时可以用 "=="（比较地址）

class Solution {
    public boolean hasCycle(ListNode head) {
        // 1.定义数组记录已访问节点 
        ListNode[] array = new ListNode[10000];
        // 2.遍历链表的每个节点， 
        while(head != null) {
            // 并与容器钟已存放的节点依次比较 
            for(int i = 0; i < array.length; i++) {
                if(array[i] == head) {
                    return true;
                }
                if(array[i] == null) {
                    array[i] = head; // 将当前节点存放到最新位置 
                    break; // 结束容器的遍历 
                }
            }
            head = head.next;
        }
        // 3.若next指针为null，则方法结束，返回false
        return false;
    }
}

时间复杂度：O(n²) -- 遍历数组 O(n)，每个节点都需要额外再遍历一次数组 O(n²)
空间复杂度：O(1) -- 固定长度 10000 的数组 O(1)
执行耗时：108 ms，击败了 5.26% 的Java用户
内存消耗：38.3 MB，击败了 99.89% 的Java用户

四. Consider 思考更优解

剔除无效代码，优化空间消耗

• 每个节点都需要遍历容器查找，比较耗时
• 按最大测试数据量创建容器，空间消耗巨大

寻找更好的算法思维

• 要证明某个节点是否第二次到达，可否将已遍历节点进行标记？
• 环形结构对应生活中的追击问题，可否使用“追击问题”模拟实现？
• 借鉴其它算法

五. Code 编码实现最优解

解法二：追击问题法 -- 思路分析

1. 定义快慢两个指针：slow = head; fast = head.next;
2. 遍历链表：
   • 快指针步长为 2：fast = fast.next.next;
   • 慢指针步长为 1：slow = slow.next;
3. 当且仅当快慢指针重合，有环，返回 true
4. 快指针为 null，或其 next 指向 null，没有环，返回 false，操作结束

边界问题

• fast 和 fast.next 指针的非空判断
• slow.next 指针不需要非空判断
  若有环，则始终有：slow.next != null
  若无环，则 fast 或 fast.next 先为空

细节问题

• 需要注意：由于 fast 的步长为 2，因此 fast == null 和 fast.next == null 都需要判断

class Solution {
    public boolean hasCycle(ListNode head) {

        //0.非空判断
        if (head == null) return false;

        //1.声明快慢两个指针
        ListNode slow = head;
        ListNode fast = head.next;

        //2.利用短路特性，先判断 fast 是否为空，再判断 fast.next 是否为空
        while (slow != fast && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow == fast;
    }
}

时间复杂度：O(n) -- 遍历链表 O(n)
空间复杂度：O(1) -- 两个指针变量 O(1)
执行耗时：0 ms，击败了 100% 的Java用户
内存消耗：38.8 MB，击败了 88.78% 的Java用户

六. Change 变形与延伸

题目变形

• （练习）分别使用 head 和 head.next 作为链表的 快/慢 指针
• （练习）标记值法：对节点的 val 属性进行标记，赋一个超出合法范围的值
• （练习）hash 表法

延伸扩展

• 龟兔赛跑问题，追击问题
• 地球，火星与太阳连为一线的问题