环形链表

[Sunny-117]

No description provided.

[lxy-Jason]

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let cur = head;
    while(cur){
        if(cur.dirty){ //加个标记,如果有环,这个标记就知道已经遍历过了
            return true
        }
        cur.dirty = true
        cur = cur.next;
    }
    return false
};

[xiaodye]

哈希法

/**
 * 链表节点类
 */
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

/**
 * 给定一个链表，判断链表中是否有环。
 * @param head
 * @returns
 */
const detectCycle = function (head: ListNode | null): boolean {
  const visted = new Set<ListNode>();

  while (head) {
    if (visted.has(head)) return true;
    visted.add(head);
    head = head.next;
  }
  return false;
};

[Pcjmy]

题目链接：https://leetcode.cn/problems/linked-list-cycle
时间复杂度：O(n)
解题思路：将访问过的结点打上标记，访问到有标记的点说明有环，否则说明无环

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    while(head)
    {
        if(head.tag) return true;
        head.tag=true;
        head=head.next;
    }
    return false;
};