leetcode：环形链表

描述：

题解：

思路一：哈希表

前面在做两数之和的问题时，使用到了哈希表的解法。对于这道题，同样地我们可以把访问过的节点存在哈希表里面，通过检查节点之前是否访问过来判断是否是环形链表。

ES6

/**
 * 判断链表是否有环
 * @param {ListNode} head 
 * @return {ListNode}
 */
export function hasCycle(head) {
  const map = new Map()
  while (head) {
    if (map.has(head)) {
      return true
    }
    map.set(head, true)
    head = head.next
  }
  return false
}

时间复杂度：O(n)
空间复杂度：O(n)

思路二：双指针快慢指针

在解决链表的问题时，感觉用指针才是最标准的解法，可以训练大家对链表这种结构的算法思维。这道题可以想象成在一个环形的跑道上速度不同的跑步者相遇的问题。这里用了两个指针，一个快指针，每次走两步；一个慢指针，每次走一步。如果是环形链表，最终快指针会和慢指针相遇。如果想验证这种思路是否是正确的，可以在纸上画一下，分奇偶链表两种情况。

ES6

/**
 * 判断链表是否有环，双指针快慢指针解法
 * @param {ListNode} head 
 * @return {ListNode}
 */
export function hasCycle(head) {
  let slowPos = head, fastPos = head
  while (fastPos) {
    if (fastPos.next == null) {
      return false
    }
    slowPos = slowPos.next
    fastPos = fastPos.next.next
    if (slowPos == fastPos) {
      return true
    }
  }
  return false
}

时间复杂度：O(n)
空间复杂度：O(1)

PS: 自己用ES6实现了下环形链表的数据结构

//声明一个链表结点
export class ListNode {
  constructor(val) {
    this.val = val
    this.next = null
  }
}

/**
 * 数组转链表
 * @param {Array} arr 
 * @return {ListNode} 
 */
export function array2List(arr) {
  if (arr.length === 0) {
    return null
  }
  const head = new ListNode(null);
  let i = 0, curr = head
  for (i; i < arr.length; i++) {
    curr.next = new ListNode(arr[i])
    curr = curr.next
  }
  return head.next
}

/**
 * 
 * 环形链表实现
 * head = [3,2,0,-4], pos = 1
 * 3->2->0->-4->2->0->-4->2...
 * @param {Array} arr 
 * @param {Integer} index 
 * @return {ListNode}
 */
export function cycleList(arr, index) {
  const linkedList = array2List(arr)
  let i = 1, circle, p = linkedList
  while (p.next) {
    if (i == index + 1) {
      circle = p
    }
    p = p.next
    ++i
  }
  p.next = circle
  return linkedList
}