Problem
Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space?
Solution
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
var slow = head;
var fast = head;
while (slow && fast) {
slow = slow.next;
fast = fast.next ? fast.next.next : undefined;
if (slow === fast) return true;
}
return false;
};
Explain:
fast
每次走两步,slow
每次走一步,如果链表有环的话,它们最终会相遇。
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).