Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Detecting Cycle in a singly link list

linked list

  • Please log in to reply
5 replies to this topic

#1 fkl

fkl

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 417 posts

Posted 15 May 2011 - 03:10 AM

Problem: Given a singly Link List, how to determine if it contains a cycle.


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.

LinkListCycle.jpg

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.

  • 1

#2 Flying Dutchman

Flying Dutchman

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1090 posts
  • Location:::1
  • Programming Language:C++, Python

Posted 16 May 2011 - 02:42 PM

I wish you were my programming professor. I really like those tutorials; explained into details but kept really simple. Keep them up! :)
  • 0

The roots of education are bitter, but the fruit is sweet.


#3 fkl

fkl

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 417 posts

Posted 17 May 2011 - 09:51 AM

Thanks a lot Dutchman, it is good to hear that others find these experiences useful and motivates to produce more of them.

I was taught programming by a really brilliant teacher who apart from concepts, highly encouraged me to enjoy the depth of programming. He put bare minimum value on syntax and focused on flow charting at a much more complex level. So we learned programming logic and why's before the how's. Also it was his style that developed interest in problem solving and coding contests.

I believe that has a lot of impact on my expression i.e. use problems to learn techniques. They help to almost immediately see the utility of a data structure, approach or logic.

I latter found out other places supporting this way of learning how to program. For e.g. MIT teaches a course "Structure and Interpretation of Computer Programs" using Scheme (Lisp). One of the reasons for choosing that language is (as mentioned in the book itself with the same name) that syntax is completed in barely a single class. So people worry about the idea of programming and develop thinking to solve actual problems BEFORE they learn how a particular language supports a specific construct.
  • 0

#4 sami1592

sami1592

    CC Lurker

  • Just Joined
  • Pip
  • 1 posts

Posted 10 August 2015 - 07:16 PM

yes I have to agree, I wish you were my teacher. the way you explained the problem is awesome! 

 

I normally do not "create account" in a unknown or unfamiliar forum, and I am visiting this forum for the first time. But I had to make an exception and create an account just to leave this comment. 


  • 0

#5 Gikoskos

Gikoskos

    CC Newcomer

  • Member
  • PipPip
  • 21 posts

Posted 10 August 2015 - 11:22 PM

Great tutorial fkl! Also thanks for the interesting problem, I never thought about before.


  • 0

#6 fkl

fkl

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 417 posts

Posted 12 August 2015 - 01:16 PM

Thanks sami and gikoskos. I am glad people could still find use of my posts several years latter. Feel free to ping for any questions.


  • 0
Today is the first day of the rest of my life





Also tagged with one or more of these keywords: linked list