Posts Tagged ‘programming’

Consider a doubly linked list whose structure of the node looks like this:

struct node
 struct node *arbitrary; /* can point to any node, including self or NULL */
 int data;
 struct node *next;      /* always points to the next node */

The next pointer points to its immediate next node, unless it is the last node, which obviously points to NULL. The arbitrary node can point to any other node in the list, including itself or NULL. We need to create a clone of the original doubly linked list – this will mean, the clone should preserve the structure / connectivity of the original, as well as the data.

Upon trying to understand the problem and to start thinking about the solution, we might initially feel an O(n) solution is not possible, or we might need to use a Hash data structure, and all such strange thoughts. The arbitrary field of first node can point to last node, the last node’s arbitrary can point to second node. How to bookkeep such information? The length of the list can be thousand or million or more.

So, this problem need to be solved without using temporary variables / arrays, and should run in time polynomial to length of list, ie. with space complexity O(1) and time complexity O(n).


In linux, the way to print a colored text in the terminal using a C program or any scripting is to exploit the terminal command according to the need.

#include <stdio.h>

#define red   "\033[0;31m"        /* 0 -> normal ;  31 -> red */
#define cyan  "\033[1;36m"        /* 1 -> bold ;  36 -> cyan */
#define green "\033[4;32m"        /* 4 -> underline ;  32 -> green */
#define blue  "\033[9;34m"        /* 9 -> strike ;  34 -> blue */

#define black  "\033[0;30m"
#define brown  "\033[0;33m"
#define magenta  "\033[0;35m"
#define gray  "\033[0;37m"

#define none   "\033[0m"        /* to flush the previous property */

 printf("%sHello, %sworld!%s\n", red, blue, none);
 printf("%sHello%s, %sworld!\n", green, none, cyan);
 printf("%s", none);

 return 0;

The output of the above code looks like this in bash terminal:

The terminal command “\ 033[0m”, which is called here as ‘none’ is required to flush the previous setting (for example, strike or underline) otherwise this property will be applied to the remaining text, no matter whatever color we set.