Not able to pass all the test cases

#1

Hi, I am trying to solve the cycle detection and removal problem, my code is able to pass 7 out of 10 test cases. However, I am not able to find the problem in my code. Here’s the code, please help me out.

#2

hello @chitwan_manchanda
check now->


#include <bits/stdc++.h>
using namespace std;

class Node
{
public:
    int data;
    Node *next;
    Node(int d)
    {
        data = d;
        next = NULL;
    }
};

// head - Head pointer of the Linked List
// Return a boolean value indicating the presence of cycle
// If the cycle is present, modify the linked list to remove the cycle as well
Node* getNode(Node* fast, Node* slow)
{
    Node* n;
    while(fast!=slow)
    {
        slow = slow->next;
        fast = fast->next;
    }
    n = slow;
    return n;
}

bool floydCycleRemoval(Node *head)
{
    Node* fast = head;
    Node* slow = head;
    Node* prev;
    Node* n;

    while(fast!=NULL and fast->next!=NULL)
    {
        fast = fast->next->next;
        slow = slow->next;

        if(fast==slow)
        {
            slow = head;
            prev = fast;
            n = getNode(fast,slow);
            while(prev->next !=n )   //updated
            {
                    prev = prev->next;
               
            }
            prev->next = NULL;
            return true;
        }
        
    }
    return false;
}

/*
*
*
*   You do not need to refer or modify any code below this. 
*   Only modify the above function definition.
*	Any modications to code below could lead to a 'Wrong Answer' verdict despite above code being correct.
*	You do not even need to read or know about the code below.
*
*
*
*/

void buildCycleList(Node *&head)
{
    unordered_map<int, Node *> hash;
    int x;
    cin >> x;
    if (x == -1)
    {
        head = NULL;
        return;
    }
    head = new Node(x);
    hash[x] = head;
    Node *current = head;
    while (x != -1)
    {
        cin >> x;
        if (x == -1)
            break;
        if (hash.find(x) != hash.end())
        {
            current->next = hash[x];
            return;
        }
        Node *n = new Node(x);
        current->next = n;
        current = n;
        hash[x] = n;
    }
    current->next = NULL;
}

void printLinkedList(Node *head)
{
    unordered_set<int> s;
    while (head != NULL)
    {
        if (s.find(head->data) != s.end())
        {
            cout << "\nCycle detected at " << head->data;
            return;
        }
        cout << head->data << " ";
        s.insert(head->data);
        head = head->next;
    }
}

int main()
{
    Node *head = NULL;

    buildCycleList(head);

    bool cyclePresent = floydCycleRemoval(head);
    if (cyclePresent)
    {
        cout << "Cycle was present\n";
    }
    else
    {
        cout << "No cycle\n";
    }

    cout << "Linked List - ";
    printLinkedList(head);

    return 0;
}
#3

It works !! thanks a lot!

#4

Can you please tell me why didn’t my code run for all cases?

#5

i have lost ur code,pls share it again.

#6
#7

why u r putting fast->next!=n this condition will stop ur prev from last updation.

this should be correct instructions->
image

#8

oky got it thnks a lot