reverse () in doubly linked list


Problem
#include <stdio.h>
#include <stdlib.h>

typedef struct DoubleLinkedListNode
{
const char *s;
struct DoubleLinkedListNode *prev, *next;

}DoubleLinkedListNode;

typedef DoubleLinkedListNode *DoubleLinkedList;


DoubleLinkedList insertLastNode(DoubleLinkedList l, const char *elem)
{
if(!l)
{
l = calloc(sizeof(DoubleLinkedListNode), 1);
l->s = elem;
}
else
{
DoubleLinkedListNode *node = l;

while(node->next)
node = node->next;

node->next = calloc(sizeof(DoubleLinkedListNode), 1);
node->next->s = elem;
node->next->prev = node;
}

return l;
}

void print(DoubleLinkedList l)
{
while(l)
{
printf("%s ", l->s);
l = l->next;
}

printf("\n");
}


DoubleLinkedList reverse(DoubleLinkedList l)
{
if(l == NULL || l->next == NULL)
return l;

DoubleLinkedList l1 = reverse(l->next);
DoubleLinkedListNode *tmp = l->next;

tmp->next = l;
l->next = l->prev;
l->prev = tmp;


return l1;
}

DoubleLinkedList reverseIterative(DoubleLinkedList l)
{
if(l == NULL || l->next == NULL)
{
printf("No reverse required");
return l;
}

DoubleLinkedListNode *tmp, *ret;
while(l)
{
tmp = l->next;

l->next = l->prev;
l->prev = tmp;

ret = l;
l = tmp;
}


return ret;
}


int main()
{
DoubleLinkedList l = NULL;

l = insertLastNode(l, "geeks");
l = insertLastNode(l, "for");
l = insertLastNode(l, "geeks");
l = insertLastNode(l, "org");
l = insertLastNode(l, "double");

print(l);

l = reverseIterative(l);

printf("\n\nAfter Reverse \n");

print(l);
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s