Problem:
Checking if linked has a cycle . This means that there will be no ‘null’ value for address pointer in linked list.
Logic:
I. Without extra space solution:
If linked list has a cycle then there never going to be a null node. So it is important to decide exit condition from loop carefully.
We will assign two nodes, one to head and one to head next. If there is cycle, then there will be a point where both temporary nodes will be pointing to same node and if there is no cycle then one of them(tempNode2 because it is assigned to next to tempNode1 at start) will become null.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public bool HasCycleCheckWithoutList(Node head) { if (head == null) return false; Node tempNode1 = head; Node tempNode2 = head.next; while(tempNode1!=null && tempNode2!=null && tempNode2.next!=null) { if (tempNode1 == tempNode2) { Console.WriteLine("Cycle exists"); return true; } tempNode1 = tempNode1.next; tempNode2 = tempNode2.next.next; } Console.WriteLine("Cycle does not exists"); return false; } |
Time complexity for this solution is O(n)
When cycle is present in linked list then tempNode1 traverse at the max n nodes and tempNode2 will traverse through linked list faster than tempNode1 and will examine n nodes. If cycle not present in Linked list then tempNode2 will become null after traversing n nodes. So time complexity of this solution is O(n).
II.Using extra list:
In this solution we will create a list and will add each node to the list if its not already present in that list. We will continue adding node till tempNode is not null.
This solution uses extra space so not feasible for long linked list.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
public bool HasCycleCheckWithList(Node head) { if (head == null) { Console.WriteLine("Linked list is empty"); return false; } if (head.next == head) { Console.WriteLine("Cycle present at head node"); return true; } bool cycle = false; Node tempNode = head; List<Node> list = new List<Node>(); list.Add(head); while(tempNode!=null) { cycle= list.Contains(tempNode.next); if(cycle==true) { Console.WriteLine("Cycle exists"); return true; } list.Add(tempNode.next); tempNode = tempNode.next; } if (cycle==false) { Console.WriteLine("No cycle present in linked list"); return false; } Console.WriteLine("Cycle exists"); return true; } |
Each new node will be compared with all its previous nodes. So for ‘n’ node there will be ‘n-1’ comparisons. So time complexity of this solution is O(n).
Space complexity of this solution is O(n).