环形链表

环形链表基本问题——如何判断链表是否成环？

快慢指针，看是否相遇

给定一个链表，判断链表中是否有环。

一个环形链表的基本修养，是能够让遍历它的游标回到原点

从 flag 出发，只要我能够再回到 flag 处，那么就意味着，我正在遍历一个环形链表。

function hasCycle(head) {
  let fast = head;
  let slow = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

function hasCycle(head) {
  try {
    JSON.stringify(head);
    return false;
  } catch (e) {
    return true;
  }
}

function hasCycle(head) {
  let cur = head;
  while (cur) {
    if (cur.flag) {
      return true;
    } else {
      cur.flag = true;
      cur = cur.next;
    }
  }
  return false;
}

环形链表衍生问题——定位环的起点

给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 null。

如果一个结点是环形链表成环的起点，那么它一定是第一个被发现 flag 标志已存在的结点.

我们遍历完这个环时，即便环上所有的结点都已经被立了 flag，但起点处的 flag 一定最先被我们定位到。因此，我们只需要在第一次发现 flag 已存在时，将对应的结点返回即可

const detectCycle = function(head) {
  let cur = head;
  while (cur) {
    if (cur.flag) {
      return cur;
    } else {
      cur.flag = true;
      cur = cur.next;
    }
  }
  return null;
};

function detectCycle(head) {
  if (!head || !head.next) return null;
  let slow = head,
    fast = head.next.next;
  while (fast && fast.next && fast !== slow) {
    slow = slow.next;
    fast = fast.next.next;
  }
  if (!fast || !fast.next) return null;
  slow = head;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next;
  }
  return slow;
}

function detectCycle(head) {
  if (!head || !head.next) return null;
  let slow = head.next,
    fast = head.next.next;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (fast == slow) {
      slow = head;
      while (fast !== slow) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow;
    }
  }
  return null;
}

快慢指针的思路

这道题还有一个公认的比较经典的思路，就是用快慢指针来做：

定义慢指针 slow，快指针 fast。两者齐头并进， slow 一次走一步、fast 一次 走两步。这样如果它们是在一个有环的链表里移动，一定有相遇的时刻。这个原理证明起来也比较简单：我们假设移动的次数为 t，slow 移动的路程就是 t，fast 移动的路程为 2t，假如环的长度为 s，那么当下面这个条件：

2t - t = s

也就是：

t = s

满足时，slow 和 fast 就一定会相遇。反之，如果两者没有相遇，同时 fast 遍历到了链表的末尾，发现 next 指针指向 null，则链表中不存在环。