判断节点有无环路

  1. class ListNode {
  2.     val: number;
  3.     next: ListNode | null;
  4.     constructor(val?: number, next?: ListNode | null) {
  5.         this.val = val === undefined ? 0 : val;
  6.         this.next = next === undefined ? null : next;
  7.     }
  8. }
  10. function hasCycle(head: ListNode | null): boolean {
  11.     let slow = head;
  12.     let fast = slow;
  13.     /*
  14.     快慢指针必然相遇， 但相遇点不一定是入环的点。 
  15.      */
  16.     while (fast !== null && fast.next !== null) { // 必要条件
  17.         slow = slow!.next;
  18.         fast = fast.next.next;
  19.         if (slow === fast) {
  20.             return true;
  21.         }
  22.     }
  24.     return false;
  25. }

  • hashmap

    1. function hasCycle1(head: ListNode | null): boolean {
    2.   let hashmap: Map<ListNode, boolean> = new Map();
    4.   while (head && head.next) {
    5.       if (hashmap.has(head.next)) {
    6.           //head.next 已经在hashpmap 中， 那么这个next必然是入环点
    7.           return true;
    8.       }
    9.       hashmap.set(head.next, true)
    10.       head = head.next;
    11.   }
    13.   return false;
    14. }