Remove Loop from Linked List | Floyd's Algorithm

Рет қаралды 12,308

5 жыл бұрын

Remove Loop or Cycle from Linked List using Floyd's Cycle Detection Algorithm.
Find First Element of Loop using Floyd's Algo: • Find beginning of cycl...
Why Floyd's Loop Detection Algorithm Works: • Why Floyd's Cycle Dete...
Detect Cycle in Linked List: • Detect Loop in Linked ...
Code is available at:
neuralnetworksai.blogspot.com...
github link: github.com/KnowledgeCenterYou...
**** Best Books For Data Structures & Algorithms for Interviews:
1. Cracking the Coding Interview: amzn.to/2WeO3eO
2. Cracking the Coding Interview Paperback: amzn.to/3aSSe3Q
3. Coding Interview Questions - Narasimha Karumanchi: amzn.to/3cYqjkV
4. Data Structures and Algorithms Made Easy - N. Karumanchi: amzn.to/2U8FrDt
5. Data Structures & Algorithms made Easy in Java - N. Karumanchi: amzn.to/2U0qZgY
6. Introduction to Algorithms - CLR - Cormen, Leiserson, Rivest: amzn.to/2Wdp8rZ
Programming Interview Questions
Crack coding interview
#Remove #Loop #Linked-List

Пікірлер: 17

@karansagar7870 4 жыл бұрын

well explained

@prateeksrivastava9 4 жыл бұрын

Great Explanation

@KnowledgeCenter 4 жыл бұрын

Thanks.

@amankumarchourasiya2279 4 жыл бұрын

There is a flaw in your code. It will fail for the test case when the starting point of the loop is the head itself.

@treyquattro 3 жыл бұрын

No it won't. This is the easiest test case - all pointers point at the same node so you can't help but get the right node to reset the next pointer!

@coderaspirant 3 жыл бұрын

Ya got your point.

@codeandtalk6 3 жыл бұрын

Can I get code for the test case u are talking about

@rahulbajetha4057 3 жыл бұрын

if(slw==head) // for circular linklist { while(slw->next!=head) slw=slw->next; slw->next=NULL; }

@sugandhm2666 2 жыл бұрын

Yes his approach doesnt work when starting point of loop is header node. However to handle that condition we can modify his code by running a while for fast node until its not slow. Below is the code public static void removeLoop(Node head){ // code here // remove the loop without losing any nodes Node slow = head; Node fast = head; while(fast!=null && fast.next!=null) { slow = slow.next; fast = fast.next.next; if(slow==fast) { if(slow==head && fast==head) { while(fast.next!=head) fast = fast.next; } else { slow = head; while(slow.next!=fast.next) { slow = slow.next; fast = fast.next; } } fast.next = null; } } }

@RaGa_BABA 2 жыл бұрын

will it work if end of loop contains head.ie: 1->2->3->4->5 and 5 has address of 1.

@adityahridyam7698 3 жыл бұрын

arre why this is working explain that.

@trilokgyaan5371 3 жыл бұрын

Unhone ek anya video me ye explain kiya hai. Why Floyd's cycle detection algorithm works. kzfaq.info/get/bejne/edljftpy2NfVnmg.html

@adityahridyam7698 3 жыл бұрын

@@trilokgyaan5371 dhanyawaad✌

@treyquattro 3 жыл бұрын

why the negativity? Substance is solid and the code is correct. Note that we actually get real code in an IDE, not scribbles on the screen like with many computer science channels.

@amankumarchourasiya2279 4 жыл бұрын

Modified version of the code is void removeLoop(Node* list) { Node *slow_p = list, *fast_p = list; while (slow_p && fast_p && fast_p->next) { slow_p = slow_p->next; fast_p = fast_p->next->next; if (slow_p == fast_p) { slow_p = list; if(fast_p == list){ while(slow_p->next != list){ slow_p = slow_p->next; } slow_p->next = NULL; } else{ while(slow_p->next != fast_p->next){ slow_p = slow_p->next; fast_p = fast_p->next; } fast_p->next = NULL; } } } }