Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
I will use the following code use in all (single) linked list programs:
struct LNode {
int data;
LNode* next;
LNode() {
next=NULL;
}
};
class LinkedList {
LNode* head;
}
For the sake of simplicity, I have put only an int field 'data' in the LNode struct. The LinkedList class currently only has a head pointer. I will add functions to it as we go along.
There are several solutions to this problem. I will discuss all of these in the following few posts. Here's a couple of them
Sol 1: Trivial Striaghtforward approach - Worst
I am not going to write code for this one, since this is the most trival approach. And this is not a solution that you want to give when you go for an interview. Basically, for this question you are given the head pointer to the linked list and nothing else. The most trivial solution invovles starting from the head and storing all the pointers in a data structure (array, dynaminc array, linked list or a hash table). Then, as you traverse the list, compare with the already visited pointers to see if you have a match. A match indicates a cycle.
This is an O(n) space and O(n^2) time solution.
Sol 2: Trivial Striaghtforward approach - Visited Field
You can use a similar approach but more efficient if you can modify the linked list data structure. Add a boolean field to the data structure indicating whether or not this field has been visited. Set the visited field to false initially. Then, as you traverse from the head, check if the node has been visited. If not set the field to true. A visited node indicates a cycle.
This is a O(n) time solution, but although it looks constant space, it is actally O(n) space (extra field for each node) when you compare it to other algorithms out there