当前位置：首页 > article >正文

数据结构与算法之链表: Leetcode 141. 环形链表 (Typescript版)

article 2024/9/24 14:30:30

环形链表

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

描述

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1

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

示例 2

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

示例 3

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

提示

链表中节点的数目范围是 [0, $10^4$ ]
- $10^5$ <= Node.val <= $10^5$
pos 为 -1 或者链表中的一个有效索引

算法实现

1 ）方案 1

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function hasCycle(head: ListNode | null): boolean {
    let p1 = head; // 单位1的速度指针
    let p2 = head; // 单位2的速度指针
    // while循环如果是环，则条件会一直为真，最终一定会相逢，即走到if中
    // while循环中如果走到了尽头，则会跳过while, 直接 return false
    while(p1 && p2?.next) {
        p1 = p1.next;
        p2 = p2.next.next;
        // 指针重逢意味着相逢，相逢意味着闭环
        if(p1 === p2) {
            return true;
        }
    }
    return false;
};

这里需要注意的是，题目示例中给定 pos，但并不是作为算法的输入参数
这一点是比较迷惑的一点，如果示例中没有相关参数，则不能参与运算
解题思路
- 两个人在圆形操场上的起点同时起跑，速度快的人一定会超过速度慢的人一圈或多圈
- 用一快一慢两个指针遍历链表，如果指针能够相逢，那么链表就有环
- 慢指针，一次走一步；快指针，每次走两步
解题步骤
- 用一快一慢两个指针遍历链表，如果指针能够相逢，就返回true
- 遍历结束后，还没有相逢就返回false

2 ）方案 2

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function hasCycle(head: ListNode | null): boolean {
    while (head?.next) {
        const node = head.next // 临时存储当前节点的下一个节点
        if (node === head) return true // 当前节点的下一个节点是自己，检测到闭环
        head.next = head // 将当前节点赋值给当前节点的下一个节点
        head = node // 将当前节点的下一个节点赋值给当前节点
    }
    return false
};

上述是官方示例，思路是基于一个点的移动，来判断是否可以找到自己
找到自己，则闭环，找不到或者没有后继，则不是闭环

3 ）方案 3

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function hasCycle(head: ListNode | null): boolean {
    let cursor = head // 初始化游标，赋值为头部节点
    const map = new Map() // 初始化Map存储结构
    while (cursor) {
        if (map.has(cursor)) return true // 检测到游标已经存在，则闭环
        map.set(cursor, true) // 存储更新游标
        cursor = cursor.next // 移动游标
    }
    return false
};