LeetCode 142: Linked List Cycle II Solution

Master LeetCode problem 142 (Linked List Cycle II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

142. Linked List Cycle II

Medium

Hash Table Linked List Two Pointers

Problem Explanation

Explanation

To detect a cycle in a linked list and find the node where the cycle begins, we can use Floyd's Tortoise and Hare algorithm. This algorithm involves two pointers moving at different speeds through the linked list. If there is a cycle, the two pointers will eventually meet at some point within the cycle.

Initialize two pointers, slow and fast, both starting at the head node.
Move the slow pointer by one node and the fast pointer by two nodes at each iteration.
If the two pointers meet at a certain node, there is a cycle in the linked list.
Move one pointer back to the head node and then move both pointers at the same pace until they meet again. The node where they meet is the starting point of the cycle.

The time complexity of this algorithm is O(n) where n is the number of nodes in the linked list. The space complexity is O(1) since we are using only two pointers.

Solution Code

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }

        return null;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 142 (Linked List Cycle II)?

This page provides optimized solutions for LeetCode problem 142 (Linked List Cycle II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 142 (Linked List Cycle II)?

The time complexity for LeetCode 142 (Linked List Cycle II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 142 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 142 in Java, C++, or Python.

Back to LeetCode Solutions