· 2 min read

Blind 75 - Linked List Cycle

Have a fast pointer and a slow pointer. fast increases by 2. slow increases by 1. if both become the same then the cycle exists. if fast one reaches end then no cycle exists.

[Video]

Check if the given LinkedList is cyclic.

Link

Approaches

O(n) time complexity; O(1) space complexity

Have a fast pointer and a slow pointer. fast increases by 2. slow increases by 1. if both become the same, then the cycle exists. if fast one reaches the end then no cycle exists.

Lines of code: 16

    public boolean hasCycle(ListNode head) {
        if(head == null) { return false;}
        ListNode slow = head;
        ListNode fast = head;
        while(fast !=null){
            slow = slow.next;
            fast = fast.next;
            if(fast==null){ break;}
            else {fast=fast.next;}
            if(slow == fast){ return true; }
        }
        return false;
    }

Line 1: head null check is unnecessary; Line 18: can be removed by adding the fast.next, check in while loop itself.

Optimized solution below

Optimized solution

Source: Java: Fast-Slow Pointer Method - LeetCode Discuss

Lines of code 8:

    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast !=null && fast.next !=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){ return true; }
        }
        return false;
    }

Without 2 pointers solution

Source: Java O(1) Memory solution - LeetCode Discuss

Modify the value in the list to something that can’t occur. Check if the current value is that value.

    public boolean hasCycle(ListNode head) {
        while (head != null) {
            if (head.val == 1_000_000) return true;
            head.val = 1_000_000;
            head = head.next;
        }
        return false;
    }

Back to Blog