Detect a loop in a Linked List

Suppose you are given a linked list like this:


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.

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…!!!



Strace – a useful debugger in linux

I recently started working on a Project to port the GTK based pavucontrol to Qt.Not only this port will add a good gui in Qt to control pulseaudio but also I plan on adding some new features like equalizer to it.I have named it lxmixer as I am developing it primarily for LXQT Desktop Environment.It will be a nice addition to gui-toolkits of LXQT.For this, I started with the source code of pavucontrol.I cloned it from the pavucontrol’s git repo and then compiled it with the following commands:


In first attempt, configure worked fine but make started giving error about not having the rule to make README file. I solved this by looking at AUR package of pavucontrol-git in archlinux. It included a command to create README file in /doc folder using touch command. After that , make compiled it successfully.

But after I ran the compiled pavucontrol binary, it gave me an error “terminate due to exception thrown by Glib:FileError.Core Dumped”.
I googled a lot about this.
Most people having such issues use gdb to debug the program.
I also used gdb to debug the program and generate backtrace using it.

gdb ./pavucontrol
>> run
>> backtrace
>> quit

Gdb backtrace info was not much Helpful.
But after some more googling, I found a forum post containing the same error as mine and the author had used strace command to generate backtrace.
At first, I thought it was some kind of command used in gdb interpreter.
but then i found that it was seperate application from gdb.
I quickly installed it using pacman
and generated trace output using strace.

strace ./pavucontrol

And Wholla !!!! It gave me the exact reason why the error occured and where it occured.It was due to
some file not found error in importing a .glade(gtk UI Designer file).It was searching the glade file in a location where the .glade file was not present.I fixed the error by making changes to source code to search in the current build directory.
And, after making this change, the compiled pavucontrol binary ran successfully with no error or warnings at all.
Now, I can start working on porting it to Qt.I hope to complete it in 2-3 weeks.