Detect a loop in a Linked List

Suppose you are given a linked list like this:

linked-list-loop

And you want to remove the loop in it.

A very trivial way can be storing a boolean “visited” variable which stores true or false depending on whether a node is visited or not. But we need to store this info in each and every node. This will cost us some space.

A very clever way is to use two pointer for traversing the linked list. one pointer will travel one node at a time and other node will travel two nodes at a time. we can also call the pointers as slowpointer and fastpointer. Now, if there is a loop in a linked list , these two pointers will meet at a certain node.

The above mentioned algorithm was proposed by Robert Floyd and is also called Floyd’s loop detection algorithm.

so, this is how we detect a loop in a Linked List.

Advertisements

GDB – a useful tool

I have just started hacking with Libreoffice. For that I downloaded the source code of libreoffice and tried building it on my ArchLinux and Windows 8. But the build was failing in both the cases somewhere in the unit test portion. I posted my problem on libreoffice mailing list about the segmentation fault I was getting during the build. One of the developers mentioned to me about using “gdb” to print the backtrace of the segmentation fault. That’s where I learnt about this new tool called “gdb” or GNU debugger which is a very useful tool for debugging programs. so, here’s how to debug programs with gdb.

First, into a terminal type:

gdb program-name

After running it , you will enter into the gdb interactive prompt:

at the prompt type “run” to start the execution of the program.

Now , if at any point, your program crashes, gdb will stop the execution of the program at that point.

now , type “bt” command at the prompt to generate the backtrace of execution and get the exact file which caused the problem.

Happy Debugging…!!!