Leetcode-141.js

/**
 * 141. Linked List Cycle
 * https://leetcode.com/problems/linked-list-cycle/
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
// 我的双指针解法（比常规的解法优雅）
const hasCycle = (head) => {
  if (head === null) return false  
  let slow = head, fast = head.next
  while (fast && fast.next) {
    if (fast == slow) return true
    slow = slow.next
    fast = fast.next.next
  }
  return false
};

// 常规双指针解法
const hasCycle = (head) => {
  if (!head || !head.next) return false
  let slow = head, fast = head.next
  while (slow != fast){
    if (!fast || !fast.next) return false;
    slow = slow.next;
    fast = fast.next.next;
  }
  return true;
};

/**
 * Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

 

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.


Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.


Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.


 

Follow up:

Can you solve it using O(1) (i.e. constant) memory?
 */