This is an interesting problem often misunderstood in the very definition. I will proceed by clarifying the requirements. A list containing a cycles doesn’t necessarily means a Circular list i.e.
In the above linked list with four nodes, D is NOT pointing to A, which is head. It is instead pointing to B or any other node. This is a list with a cycle. However, it is NOT a circular list. A circular list is one in which the last node i.e. tail is pointing towards the head always.
Before we move ahead let me lay out the structure. A linked list can simply be represented as:
struct Node // A c++ struct is automatically used as a type.
{
int data;
Node *next;
};
Node * head; // The head of list is declared separately since it is the direct starting reference to list.
Then we have supporting functions such as “add node at head” which might take data value as parameter allocates a new node, assigns the value and inserts that at the head of link list.
Now the first off the head thought to solution is, traverse through the list, if you find null, there was no cycle if not, there is i.e.
Node * temp = head;
while (temp != null)
{
temp = temp->next;
}
And this is a correct solution – but wait. It only works when list does NOT have a cycle. What if it does? Will this loop terminate? When will you stop and be able to say “hey – it has a cycle”?
You can’t. The loop will keep on running indefinitely since it won’t find a null. Can you put another condition to terminate? The answer is No – there is no way to know that for sure.
So we have to find a better way. The next thought that comes to mind is, find a way to know if an element visited before is encountered again. The moment you hit this condition, you can break out of the loop and say it contains a cycle. If you encounter a null instead, you know there is no cycle.
Perfect, that is the correct solution. But think again – how are we going to implement that? As we have visited n numbers and reach n+1, you have to compare n+1 with all the previous n, one by one to know if it is any one of them. So this works but there are n * n iterations in the worst case. So complexity of this algorithm would be O (n^2).
Can we improve on this? Remember we have no assumptions about the list data, i.e. it is not sorted or does not necessarily contain distinct numbers. So a good idea will be to compare address of each element (pointer to list Node) with all the previous ones.
May be if we could come up with a hash table storing each node’s address as it comes, it will help to determine if the address came earlier and was hashed and saved. Still this would require building a hash map of size n (equivalent to the number of number of nodes in the list).
Can it be improved?
Yes – but to get to that solution let us try to solve another (but trivial) problem which will help us understand this solution better.
Finding middle element of a linked list
Suppose you a given a singly link list (no cycles). How would you find out the middle element? Do not assume the size / number of elements is known in advance.
A quick solution is, traverse through the list in a loop, incrementing a counter. When you hit null, you would know the number of elements.
Start again and go up to num elements / 2, If num was even OR (num elements / 2) + 1, if num was odd.
This is an okay solution and gets us the result. However, it would require going through the list twice apart from keeping track of even odd.
Can we do it in a single pass?
Yes - There is a simpler and more elegant solution (though not a very significant algorithmic improvement, because 1 or 2 passes are still constants that are ignored in Big O calculation).
It goes as follows – We take two pointers and both are traversed through the list. However, first is double incremented i.e. it jumps two nodes in a single iteration where as the other jumps normally i.e. one node per iteration.
This implies that when first pointer reaches the end of list, the second one is exactly in the middle.
Node *first, *second;
first = second = head;
while (first->next != null)
{
first = first->next->next; // omitted null checking of nodes for simplicity
second = second->next;
}
return second;
Why is this better? There is a single run of the entire list. One pointer skips one node each time so it touches half of list when it reaches end. The slower one second goes through every node until exactly half. So this totals out to walking the total list exactly once.
We don’t have to worry about even or odd thing too.
Why did we discuss this problem?
Because we can use the idea to find a better solution for detecting a cycle in a list.
Here is the idea: Take two pointers, one fast and one slow and start iterating the list. If the list did not contain a cycle the faster one of them is going to run into null and loop will be terminated. If a cycle does exist, the faster pointer is going to run past the slower one after going through the list. So if first == second, we know a cycle exist and can break out of the loop. This situation will never occur without a cycle and is sure to occur with a cycle.
Node *first, *second;
first = second = head;
do
{
first = first->next->next; // ommitted null checking of nodes for keeping algorithm easy to read
second = second->next;
if(first == second) // cycle found
break;
} while (first->next != null); // if this is true, the list does not contain a cycle
This can even be run with increasing the jumps of first from two to three pointers, but that would increase the number required checks for null and list termination. The pointers may not collide in one cycle but then they will after second or third cycle.
The run time of this algorithm is O (n) i.e. we went through the list at max n, 2n, or 3n times even when a cycle exists and our pointers collide as late as possible.
Edited by fayyazlodhi, 15 May 2011 - 12:03 PM.
Answered
![[C] Linked list affected by printf()? - last post by 0xDEADBEEF](http://forum.codecall.net/uploads/profile/photo-thumb-45557.jpg?_r=1402171057)
