15、环形链表

题目描述

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

解题思路

• 两个人在环形跑道上的同一起点同时起跑, 一直跑下去, 速度快的人总会超过速度慢的人一圈
• 用一快一慢两个指针遍历链表, 如果指针能够相逢, 那么该链表有环, 返回true, 遍历结束后还没有相逢就返回false

代码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
    let p1 = head // 慢指针
    let p2 = head // 快指针
    while (p1 && p2 && p2.next) {
        p1 = p1.next
        p2 = p2.next.next
        if (p1 === p2) {
            return true
        }
    }
    return false
}