I was asked to write a program to interchange numbers using doubly
linked list @ Amazon.
Here is the details with Code that i wrote.
i/p: 1 2 3 4 5 6 7 8 .....n,n-1.
o/p: 2 1 4 3 6 5 8 7.....n,n-1.
I wanted this code to make as small and it should be algorithmically
fit. The following is just plain without any logic. plz help me to
solve this algorithmically i.e big oh etc. and it should run fast for
millions of numbers.
Thanks a lot.
Code:
--------------------------------------------------------------------------------------------
#define TravelNode 8
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
/*
* Doubly linked Node with Data
*/
struct node {
int data;
struct node *prev;
struct node *next;
};
typedef struct node NODE;
int main(void) {
NODE *tempHead,
*mainHead,
*head,
*tail,
*temp;
int i=1;
/*
* Memory Allocation for head node
*/
head = (NODE*)malloc(s izeof(NODE));
/*
* Save First Node
*/
tempHead = head;
temp = head;
/*
* Fill data in very first node
*/
head->data = i++;
head->next = (NODE*)malloc(s izeof(NODE));
head->prev = NULL;
head = head->next;
head->prev = tempHead;
printf("\n Begin.... \n");
/*
* Fill Data in the Nodes
*/
while(i < TravelNode ){
head->data = i++;
head->prev = temp;
temp = head;
head->next = (NODE*)malloc(s izeof(NODE));
head = head->next;
head->prev = temp;
}
head->data = i;
head->prev = temp;
head->next = NULL;
head = tempHead; // head pointing to
First Node Now.
tail = head->next; // tail pointing to
Second Node.
mainHead = tail->next; // mainHead Points to 3rd Node.
/*
* First Two Node Exchange
*/
temp = (NODE*)malloc(s izeof(NODE));
temp = head->prev;
head->prev = head->next;
head->next = tail->next->next;
tail->next = tail->prev;
tail->prev = temp;
temp = head->prev;
mainHead = temp; // This will be used
for final printing of Data
from resulted db list
/*
* Node interchange Kernel
*/
while(head->next != NULL){
head = head->next->prev;
tail = head->next;
temp = head->prev;
if(head->next == NULL){
head->prev = head->next;
head->next = tail->next;
tail->next = tail->prev;
tail->prev = temp;
head->next = NULL;
}
else {
head->prev = head->next;
if(!(tail->next))
head->next = tail->next;
else
head->next = tail->next-
>next;tail->next = tail->prev;
tail->prev = temp;
}
}
printf("\n");
i = TravelNode;
while(i-- 0){
printf(" R = %d ", mainHead->data);
mainHead = mainHead->next;
}
free(mainHead);
printf("\n End.... \n");
----------------------------------------------------------------------------------------------------------------
