141. Linked List Cycle

Solution

Use a slow and fast moving pointers. The fast pointer moves at double the speed.

  • If there is no cycle the fast pointer will reach the end before the slow pointer.
  • If there is a cycle the two pointers will meet again.

More precisely the fast pointer will always meet the slow pointer on the same spot, so we just need to check if fast === slow.

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if (!head || !head.next) {
        return false;
    }
    
    let slow = head;
    let fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (fast === slow) {
            return true;
        }
    }
    
    return false;
};

The algorithm used is called Floyd’s Tortoise and Hare Algorithm.

For a more in-depth explanation check this video:

Complexity

  • Time Complexity: O(N), because the two pointers will meet after N iterations in the worst case.
  • Space Complexity: O(1), because we don’t use any extra memory.

All Solutions