rahul300chaudhary400
BAN USERC Code:
First the header file to create double circular linked list:
#include <stdio.h>
#include <stdlib.h>
#ifndef __DATASTRUCTURE
#define __DATASTRUCTURE
typedef struct node
{
int id;
struct node *next;
struct node *prev;
} Node;
Node* createNextNode(int id, Node *callingNode)
{
Node *temp = (Node*)malloc(sizeof(Node));
temp>id = id;
if (callingNode != NULL)
{
temp>next = callingNode>next;
temp>prev = callingNode;
callingNode>next = temp;
temp>next>prev = temp;
}
else
{
temp>next = temp;
temp>prev = temp;
}
return temp;
}
void deleteNode(Node *unwantedNode)
{
unwantedNode>prev>next = unwantedNode>next;
unwantedNode>next>prev = unwantedNode>prev;
free(unwantedNode);
}
void printNodesForward(Node *startNode)
{
Node *temp = startNode;
do
{
printf("%d\t", temp>id);
temp = temp>next;
}while(temp != startNode);
printf("\n");
}
void printNodesBackward(Node *startNode)
{
Node *temp = startNode;
do
{
printf("%d\t", temp>id);
temp = temp>prev;
}while(temp != startNode);
printf("\n");
}
#endif
Then the actual code to remove every kth node in o(n) time. Note that the traversal to reach the nth node takes o(n) time.
#include "dataStructure.h"
int main(int argc, char **argv)
{
if (argc != 3)
{
printf("Usage: ./a.out <totalNodes> <jumpBy>\n");
return 1;
}
int totalNodes = atoi(argv[1]);
int jumpBy = atoi(argv[2]) % totalNodes;
Node *callingNode = createNextNode(1, NULL);
Node *startNode = callingNode;
int i = 2;
do
{
callingNode = createNextNode(i, callingNode);
i++;
}while(i != totalNodes+1);
while(totalNodes != 1)
{
for (i = 1; i != jumpBy; i++)
{
startNode = startNode>next;
}
Node *unwantedNode = startNode;
startNode = startNode>next;
deleteNode(unwantedNode);
printNodesForward(startNode);
totalNodes;
}
return 0;
}

rahul300chaudhary400
June 30, 2013 Oh now I get the question. I understood it completely wrong. Thanks.
 rahul300chaudhary400 June 26, 2013Please care to tell me why the solution is wrong.
 rahul300chaudhary400 June 26, 2013You can arrange the nodes as the distance from their center. What I have done here is defined a simple list, and each element of list is a node that describes the distance from the center. Then from that list I retrieve an element randomly and delete it. I do that until there is one element left.
I could have also done it sequentially i.e delete node 1, node 2.... node n1
Or I could have made a function to delete the userspecified node until one last element is left.
import random
nodes = list()
for i in range(0, 5):
n = input("Enter distance from circle: ")
n = int(n)
nodes.append(n)
def pickRandom(start, end):
return random.randint(start, end)
i = len(nodes)  1
while (i != 0):
print(nodes)
del(nodes[pickRandom(0, i)])
i = i1
print(nodes)

rahul300chaudhary400
June 25, 2013
Here is my solution that uses multistructured linked list to solve the problem:
"I know its a bit complicated, but when you will run the code, you will know that it works". :)
The solution might seem a bit complicated because I have modified the problem to also hold relations to other node data such as distance between two nodes, to make the problem more challenging.
Each node contains its ID and a link to another structure called Link. This "structure", Link is a linked list where each node of this link list tells what other nodes this node is connected to.
Link contains two fields. One field points to the actual structure (Relation) where all the data is kept such as what is the distance to the other node and what node it is connected to.
The other field just points to the next structure.
The header file goes as follows:
And the main file goes as follows:
 rahul300chaudhary400 July 02, 2013