What is the time complexity of Linked List Cycle II?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Linked List Cycle II?

This problem uses Hash Table, Linked List, Two Pointers. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Linked List Cycle II?

Insight 1: The 'fast and slow pointer' technique (Floyd's Cycle-Finding Algorithm) is essential for detecting cycles in a linked list without using extra space. If a cycle exists, the fast pointer will eventually catch up to the slow pointer. Insight 2: The distance from the head of the list to the cycle's starting node is equal to the distance from the meeting point of the fast and slow pointers to the cycle's starting node.

Which companies ask LeetCode 142. Linked List Cycle II in interviews?

This problem is frequently asked at Paytm, Ripple, TikTok.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Linked List Cycle II - LeetCode 142 Solution

Linked List Cycle II - Complete Solution Guide

Linked List Cycle II is LeetCode problem 142, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null . There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to ( 0-indexed ). It is -1 if there is no cycle. Note that pos is not passed as a parameter . Do not modify the linked list. Example 1: Input: head = [3,2,0,-4

Detailed Explanation

The problem asks us to detect if a cycle exists in a given linked list and, if so, to find the node where the cycle begins. A cycle means that at some point, following the `next` pointers leads back to a previously visited node, forming a loop. The input is the `head` of the linked list. The output is the node where the cycle begins, or `null` (or `nullptr` or `NULL` depending on the language) if no cycle exists. We are not given the position of the cycle's start, and we cannot modify the linked list. The challenge is to solve this in O(1) space.

Solution Approach

The solution uses Floyd's Cycle-Finding Algorithm, also known as the 'tortoise and hare' algorithm. First, we use two pointers, `slow` and `fast`, initialized to the `head` of the list. The `slow` pointer moves one node at a time, while the `fast` pointer moves two nodes at a time. If there is a cycle, the `fast` pointer will eventually catch up with the `slow` pointer. Once they meet, we reset one of the pointers (usually `ptr`) to the `head` of the list. Then, we move both `ptr` and `slow` one node at a time until they meet again. The node where they meet is the starting node of the cycle.

Step-by-Step Algorithm

Step 1: Initialize two pointers, `slow` and `fast`, both pointing to the `head` of the linked list.
Step 2: Iterate through the linked list using a `while` loop as long as `fast` and `fast.next` are not `null` (to avoid NullPointerExceptions).
Step 3: Inside the loop, move `slow` one step forward (`slow = slow.next`) and `fast` two steps forward (`fast = fast.next.next`).
Step 4: Check if `slow` and `fast` are equal. If they are, it means a cycle exists. Break out of the outer `while` loop.
Step 5: If the outer `while` loop completes without `slow` and `fast` meeting, it means there is no cycle. Return `null`.
Step 6: If a cycle exists, initialize another pointer `ptr` to the `head` of the linked list.
Step 7: Move `ptr` and `slow` one step at a time until they meet (`ptr = ptr.next` and `slow = slow.next`).
Step 8: The node where `ptr` and `slow` meet is the starting node of the cycle. Return `ptr`.

Key Insights

Insight 1: The 'fast and slow pointer' technique (Floyd's Cycle-Finding Algorithm) is essential for detecting cycles in a linked list without using extra space. If a cycle exists, the fast pointer will eventually catch up to the slow pointer.
Insight 2: The distance from the head of the list to the cycle's starting node is equal to the distance from the meeting point of the fast and slow pointers to the cycle's starting node.
Insight 3: Correctly handling edge cases such as an empty list or a list without a cycle is crucial for a robust solution.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Hash Table, Linked List, Two Pointers.

Companies

Asked at: Paytm, Ripple, TikTok.

Linked List Cycle II | LeetCode 142

Medium

Hash Table Linked List Two Pointers

Time: O(n)Space: O(1)

Solution Code

Available in:

/**
 * 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) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // Cycle detected, find the start of the cycle
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        
        return null;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 142: Linked List Cycle II - Detailed explanation and solution approaches.

Topics

Hash Table Linked List Two Pointers

Companies

PaytmRippleTikTok

Stats

Difficulty:Medium

Languages:4

Companies:3

Problem #:142

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Initialize two pointers, `slow` and `fast`, both pointing to the `head` of the linked list.
2
Step 2: Iterate through the linked list using a `while` loop as long as `fast` and `fast.next` are not `null` (to avoid NullPointerExceptions).
3
Step 3: Inside the loop, move `slow` one step forward (`slow = slow.next`) and `fast` two steps forward (`fast = fast.next.next`).
4
Step 4: Check if `slow` and `fast` are equal. If they are, it means a cycle exists. Break out of the outer `while` loop.
5
Step 5: If the outer `while` loop completes without `slow` and `fast` meeting, it means there is no cycle. Return `null`.
6
Step 6: If a cycle exists, initialize another pointer `ptr` to the `head` of the linked list.
7
Step 7: Move `ptr` and `slow` one step at a time until they meet (`ptr = ptr.next` and `slow = slow.next`).
8
Step 8: The node where `ptr` and `slow` meet is the starting node of the cycle. Return `ptr`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The `while` loops iterate through the linked list. The first loop (fast and slow pointers) has a time complexity of O(k) where k is the length until the collision point. The second loop (ptr and slow pointers) has a time complexity of O(m) where m is the length until the start of the cycle. Because both depend on the size of the list and are sequential, the overall complexity is O(k + m) which simplifies to O(n).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Hash Table

We can use a hash table (or set) to store the nodes we visit. As we traverse the linked list, we check if the current node is already in the hash table. If it is, we have found a cycle, and the current node is the starting node of the cycle. If we reach the end of the list without finding a cycle, there is no cycle.

Time: O(n), where n is the number of nodes in the linked list.Space: O(n), because in the worst case, we might need to store all the nodes in the hash table.

Trade-offs: The hash table approach is easier to understand and implement, but it uses O(n) space. The Floyd's algorithm is more space-efficient (O(1)) but requires a more complex understanding of the underlying math and logic. Use the hash table approach if space is not a major concern and simplicity is preferred; use Floyd's algorithm when space is a critical constraint.

✨

Key Insights

1Insight 1: The 'fast and slow pointer' technique (Floyd's Cycle-Finding Algorithm) is essential for detecting cycles in a linked list without using extra space. If a cycle exists, the fast pointer will eventually catch up to the slow pointer.
2Insight 2: The distance from the head of the list to the cycle's starting node is equal to the distance from the meeting point of the fast and slow pointers to the cycle's starting node.
3Insight 3: Correctly handling edge cases such as an empty list or a list without a cycle is crucial for a robust solution.

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Linked List

Elements connected via pointers. Like a chain where each link knows the next.

Edge Cases

Edge case 1: Empty linked list (head is null). The code handles this correctly because the `while` loop condition (`fast && fast.next`) will immediately evaluate to false, and the function will return `null`.
Edge case 2: Linked list with only one node and no cycle. The `while` loop condition (`fast && fast.next`) will evaluate to false because `fast.next` will be `null`, and the function will correctly return `null`.
Edge case 3: Linked list with a cycle starting from the head. The algorithm correctly identifies the head as the starting point of the cycle.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not checking for `null` before accessing `fast.next` and `fast.next.next`, which can lead to NullPointerExceptions.

✗Common mistake 2: Forgetting to reset one of the pointers to the `head` of the list after the slow and fast pointers meet. This step is crucial for finding the actual starting node of the cycle.

✗Common mistake 3: Thinking that after the fast and slow pointers collide, the slow pointer is at the start of the cycle. It requires an additional calculation using ptr started from head to calculate where the cycle begins

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Detecting infinite loops in software. Similar to how this algorithm detects cycles in linked lists, it can be adapted to detect infinite loops in program execution by monitoring function calls or code execution paths.

🏦Real-world scenario 2: Data corruption detection in blockchain. In blockchain networks, cycles in transaction chains or data structures can indicate malicious activity or data corruption. This algorithm can be applied to identify such cycles and ensure data integrity.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 21, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

❓

Frequently Asked Questions

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

Why use a dummy node in linked list problems?

A dummy node simplifies edge cases where the head might change (insertion/deletion at head) or when building a new list. Initialize dummy.next = head, work with dummy.next throughout, and return dummy.next at the end to handle all cases uniformly.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Linked List Cycle II"?

For this medium-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether linked list techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?