algoadvance

Leetcode 142. Linked List Cycle II

Problem Statement

LeetCode Problem 142: Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent the 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 form a cycle. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Clarifying Questions

  1. What should we return if there is no cycle detected?
    • We should return null.
  2. Can we assume that the input list isn’t empty?
    • Yes, but it’s worth handling the case where the linked list is null to avoid null pointer exceptions.
  3. What is the definition of a cycle in a linked list?
    • A cycle occurs if a node’s next pointer points back to a previous node, creating a loop.
  4. Is there any constraint on the values of the nodes?
    • No, the values of the nodes do not affect the presence or absence of a cycle.

Strategy

To solve this problem, we can use Floyd’s Tortoise and Hare algorithm, which consists of two main steps:

  1. Cycle Detection: Use two pointers, a slow pointer (slow) that moves one step at a time, and a fast pointer (fast) that moves two steps at a time. If there’s a cycle, the fast pointer will eventually meet the slow pointer within the cycle.
  2. Cycle Start Detection: If a cycle is detected, reset one of the pointers to the head of the list and move both pointers one step at a time. The point at which these two pointers meet will be the start of the cycle.

Code

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

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        // Step 1: Detect if there is a cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // Cycle detected
                break;
            }
        }

        // If there is no cycle
        if (fast == null || fast.next == null) {
            return null;
        }

        // Step 2: Find the entry point to the cycle
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow; // The start of the cycle
    }
}

Time Complexity

This is the most efficient solution for the problem, as it finds the cycle and its starting node using the least possible amount of time and space.

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