Skip to content

· 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;
    }

Get new posts by email

No spam. Unsubscribe anytime. Or grab the RSS feed.

Mailto-based for now. ButtonDown / ConvertKit can replace this form later.


Comments lazy-load on scroll. Prefer GitHub? Giscus activates once PUBLIC_GISCUS_* env vars are set (see Giscus.astro).

Index

Index

Back to Blog