## Friday, May 18, 2007

### How do you reverse a singly linked list? How do you reverse a doubly linked list? Write a C program to do the same.

This is THE most frequently asked interview question. The most!.

Here are a few C programs to reverse a singly linked list.

Method1 (Iterative)

#include "stdio.h"

// Variables

typedef struct node {

int value;

struct node *next;

}mynode;

// Globals (not required, though).

// Functions

// The main() function

int main()

{

//Print it

print_list();

// Reverse it.

iterative_reverse();

//Print it again

print_list();

return(0);

}

// The reverse function

void iterative_reverse()

{

mynode *p, *q, *r;

{

return;

}
p = head; q = p->next;

p->next = (mynode *)0;

while (q != (mynode *)0)

{

r = q->next;

q->next = p;

p = q; q = r;

}

}

{

temp = (mynode *) malloc(sizeof(struct node));

temp->next=(mynode *)0;

temp->value=value;

{

tail=temp;

}

else

{

tail->next=temp;

tail=temp;

}

}

// Function to print the linked list.

void print_list()

{

printf("\n\n");

{

printf("[%d]->",(temp->value));

}

printf("[NULL]\n\n");

}

Method2 (Recursive, without using any temporary variable)

#include "stdio.h"

// Variable

stypedef struct node

{

int value;

struct node *next;

} mynode;

// Globals.

// Functions

mynode* reverse_recurse(mynode *root);

void print_list();

// The main() function

int main()

{

//Print it

print_list();

// Reverse it.

{

temp->next = (mynode *)0;

}

//Print it again

print_list();

return(0);

}

// Reverse the linked list recursively//
// This function uses the power of the stack to make this// *magical* assignment//// node->next->next=node; //// :)
mynode* reverse_recurse(mynode *root)

{

if(root->next!=(mynode *)0)

{

reverse_recurse(root->next);

root->next->next=root;

return(root);

}

else

{

}

}

{

temp = (mynode *) malloc(sizeof(struct node));

temp->next=(mynode *)0;

temp->value=value;

{

tail=temp;

}

else

{

tail->next=temp;

tail=temp;

}

}

// Function to print the linked list.

void print_list()

{

printf("\n\n");

{

printf("[%d]->",(temp->value));

} printf("[NULL]\n\n");

}

Method3 (Recursive, but without ANY global variables. Slightly messy!)

#include "stdio.h"

// Variablestypedef

struct node

{

int value;

struct node *next;

}mynode;

// Functions

mynode* reverse_recurse(mynode *current, mynode *next);

void print_list(mynode *);

int main()

{

//Print it

// Reverse it.

//Print it again

getch();

return(0);

}

// Reverse the linked list recursively

mynode* reverse_recurse(mynode *current, mynode *next)

{

mynode *ret;

if(current==(mynode *)0)

{

return((mynode *)0);

}

ret = (mynode *)0;

if (current->next != (mynode *)0)

{

ret = reverse_recurse(current->next, current);

}

else

{

ret = current;

}

current->next = next;

return ret;

}

// Takes pointers to pointers to maintain the // *actual* head and tail pointers (which are local to main()).

{

mynode *temp1, *temp2;

temp1 = (mynode *) malloc(sizeof(struct node));

temp1->next=(mynode *)0;

temp1->value=value;

{

*tail=temp1;

}

else

{

for(temp2 = *head; temp2->next!= (mynode *)0; temp2=temp2->next);

temp2->next = temp1; *tail=temp1;

}

}

// Function to print the linked list.

{

mynode *temp;

printf("\n\n");

{

printf("[%d]->",(temp->value));

}

printf("[NULL]\n\n");

}

This is really easy, just keep swapping the prev and next pointers and at the end swap the head and the tail:)

#include "stdio.h"

#include "ctype.h"

typedef struct node

{

int value;

struct node *next;

struct node *prev;

} mynode ;

void print_list();

void reverse();

int main()

{

tail=NULL;

print_list();

reverse();

print_list();

return(1);
}

{

mynode *temp, *cur;

temp = (mynode *)malloc(sizeof(mynode));

temp->next=NULL;

temp->prev=NULL;

{

tail=temp;

temp->value=value;
}

else

{

cur->next=temp;

temp->prev=cur;

temp->value=value;

tail=temp;
}
}

void print_list()

{

mynode *temp;
printf("\n--------------------------------\n");

{

printf("\n[%d]\n",temp->value);

}
}

void reverse()

{

mynode *cur, *temp, *save_next;

{

printf("\ncur->value : [%d]\n",cur->value);

temp=cur->next;

save_next=cur->next;

cur->next=cur->prev;

cur->prev=temp;

cur=save_next;

}