algoadvance

Leetcode 141. Linked List Cycle

Problem Statement

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where the tail connects to. If pos is -1, then there is no cycle in the linked list.

Clarifying Questions

  1. Input Format: What is the format of the input linked list? Will it be passed as an argument to a function in the form of a head node?
    • Answer: Yes, the linked list will be passed to the function as the head node.
  2. Output Format: What should be the output if a cycle is detected or not?
    • Answer: The function should return true if a cycle is detected, otherwise it should return false.

Strategy

To detect a cycle in a linked list, we can use Floyd’s Tortoise and Hare algorithm. This algorithm uses two pointers:

If there is no cycle, the fast pointer will eventually reach the end of the list. If there is a cycle, the fast pointer will meet the slow pointer within the cycle.

Code

Here’s how we can implement this in Java:

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

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

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI