Reversing a Singly Linked List

This article is part of article series - "Datastructures"

Previous Article: Deleting a Node from a Singly Linked List.
Next Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.

Let us see how to reverse a Singly Linked List.

Figure-1: Singly Linked List

Pseudocode:

cur_ptr = HEAD->NEXT
prev_ptr = NULL

forever:

   if cur_ptr == NULL
   break

   tmp_ptr  = prev_ptr
   prev_ptr = cur_ptr
   cur_ptr  = cur_ptr->NEXT
   
   prev_ptr->NEXT = tmp_ptr

HEAD->NEXT = prev_ptr

Complexity:
Time Complexity: O(n)
Space Complexity: O(3)

If we try on the example in Figure-1 we get the output as shown below

Figure-2: After reversing the Singly Linked List

Previous Article: Deleting a Node from a Singly Linked List.
Next Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.

Detecting a Loop in Singly Linked List - Tortoise & Hare

This article is part of article series - "Datastructures"

Previous Article: Reversing a Singly Linked List.
Next Article: Finding first node in a Loop in Singly Linked List.

Eventhough there are multiple algorithms available we start with

Floyd's Cycle-Finding Algorithm
In simple terms it is also known as "Tortoise and Hare Algorithm" or "Floyd's Cycle Detection Algorithm" named after its inventor Robert Floyd. It is one of the simple cycle detection algorithm. It's a simple pointers based approach.

Robert Floyd

Write a C Program without main function

In a C program main function is the entry point so it is mandatory to have a main function.

But let us see how can we write a program without main (Kind of hiding main in some obfuscated code). This post is purely out of interest to know that we can do something weird like this, just for learning.

Implementing ls command in C

We know that ls command in unix displays the list of files in a directory. It has various options to display the data in various styles and formats.

By default its implementation is part of Coreutils package, which is default package in all Linux flavours.

I want to see how we can implement its basic functionality with a simple C program.

GIT - Adding diffmerge as visual merge in git

GIT is one of the popular distributed code repositories in opensource community, especially with developers working on opensource projects like linux kernel and others.

Operations like Merge and Diff are the most irritating & tricky tasks via command line when working on large code changes. So let us see how can we add some graphical stuff for these operations when using on GIT so that we can do merging and other options very easily.