Solving Linked List Cycle

To see the question, click here.

Naive Approach

The idea is to use a HashSet to keep track of the nodes we've visited. We know there is a cycle if we encounter a node we've already seen.

// TC: O(n)
// SC: O(n)

import java.util.HashSet;

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class LinkedListCycle {

    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode curr = head;
        while (curr != null) {
            if (set.contains(curr)) {
                return true;
            }
            set.add(curr);
            curr = curr.next;
        }
        return false;
    }

    public static void main(String[] args) {
        LinkedListCycle l = new LinkedListCycle();
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(-4);
        head.next.next.next.next = head.next;
        System.out.println(l.hasCycle(head));
    }
}

Performance

The time complexity of the hasCycle method is O(n) because, in the worst-case scenario, we may have to iterate through all the nodes in the linked list once to detect a cycle. The space complexity is also O(n) because we are using a HashSet to store visited nodes, and in the worst-case scenario, we may have to store all the nodes in the HashSet.

Refined Approach

Instead of maintaining a HashSet , we can modify the linked list structure by adding a boolean variable called visited to indicate if the node has been visited or not. This is generally not recommended because it alters the original structure.

// TC: O(n)
// SC: O(1)

class ListNode {
    int val;
    ListNode next;
    boolean visited;

    ListNode(int x) {
        val = x;
        next = null;
        visited = false;
    }
}

public class LinkedListCycle {

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

    public static void main(String[] args) {
        LinkedListCycle l = new LinkedListCycle();
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(-4);
        head.next.next.next.next = head.next;
        System.out.println(l.hasCycle(head));
    }
}

Performance

The time complexity of the hasCycle method is O(n) because, in the worst-case scenario, we may need to iterate through all n nodes in the linked list to determine whether there is a cycle. The space complexity is O(1) because we use constant extra space regardless of the input size.

Efficient Approach

Since we are dealing with a problem related to a cyclic linked list, let us try out Fast and Slow pointers. If the head is null, it means that there is no node and we return false. If thehead.next is null, it means that there is only one node without any cycle because if there is a cycle, head.next will be head itself. So, return false. We will be declaring two pointers slow and fast where slow is at head and fast is at head.next. Until slow meets fast, we will move the slow pointer one step forward, and the fast pointer two steps forward. At any stage, if the fast becomes null or fast.next becomes null, we return false because the fast pointer has visited all the nodes and hence there is no cycle. Return true if the fast meets slow.

// TC: O(n)
// SC: O(1)

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class LinkedListCycle {

    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head, fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

    public static void main(String[] args) {
        LinkedListCycle l = new LinkedListCycle();
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(-4);
        head.next.next.next.next = head.next;
        System.out.println(l.hasCycle(head));
    }
}

Performance

The time complexity of the hasCycle method is O(n) because, in the worst-case scenario, we may need to iterate through the entire linked list once to detect a cycle. The space complexity is O(1) because we are using only a constant amount of extra space regardless of the input size.

Thank you for reading!

Check out other DSA patterns here.

You can support me by buying me a book.