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!.

Singly linked lists

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).

mynode *head, *tail, *temp;


// Functions

void add(int value);void iterative_reverse();void print_list();


// The main() function

int main()

{

head=(mynode *)0; // Construct the linked list.

add(1);

add(2);

add(3);

//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;

if(head == (mynode *)0)

{

return;

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

p->next = (mynode *)0;

while (q != (mynode *)0)

{

r = q->next;

q->next = p;

p = q; q = r;

}

head = p;

}


// Function to add new nodes to the linked list

void add(int value)

{

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

temp->next=(mynode *)0;

temp->value=value;

if(head==(mynode *)0)

{

head=temp;

tail=temp;

}

else

{

tail->next=temp;

tail=temp;

}

}

// Function to print the linked list.

void print_list()

{

printf("\n\n");

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

{

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.

mynode *head, *tail, *temp;

// Functions

void add(int value);

mynode* reverse_recurse(mynode *root);

void print_list();

// The main() function

int main()

{

head=(mynode *)0;

// Construct the linked list.

add(1);

add(2);

add(3);

//Print it

print_list();

// Reverse it.

if(head != (mynode *)0)

{

temp = reverse_recurse(head);

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

{

head=root;

}

}

// Function to add new nodes to the linked list.

void add(int value)

{

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

temp->next=(mynode *)0;

temp->value=value;

if(head==(mynode *)0)

{

head=temp;

tail=temp;

}

else

{

tail->next=temp;

tail=temp;

}

}

// Function to print the linked list.

void print_list()

{

printf("\n\n");

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

{

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

void add(mynode **head, mynode **tail, int value);

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

void print_list(mynode *);

int main()

{

mynode *head, *tail;

head=(mynode *)0; // Construct the linked list.

add(&head, &tail, 1);

add(&head, &tail, 2);

add(&head, &tail, 3);

//Print it

print_list(head);

// Reverse it.

head = reverse_recurse(head, (mynode *)0);

//Print it again

print_list(head);

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;

}

// Function to add new nodes to the linked list.

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


void add(mynode **head, mynode **tail, int value)

{

mynode *temp1, *temp2;

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

temp1->next=(mynode *)0;

temp1->value=value;

if(*head==(mynode *)0)

{

*head=temp1;

*tail=temp1;

}

else

{

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

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

}

}

// Function to print the linked list.

void print_list(mynode *head)

{

mynode *temp;

printf("\n\n");

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

{

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

}

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

}



Doubly linked lists

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 ;

mynode *head, *tail;

void add_node(int value);

void print_list();

void reverse();

int main()

{

head=NULL;

tail=NULL;

add_node(1);

add_node(2);

add_node(3);

add_node(4);

add_node(5);


print_list();

reverse();

print_list();

return(1);
}

void add_node(int value)

{

mynode *temp, *cur;

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

temp->next=NULL;

temp->prev=NULL;

if(head == NULL)

{
printf("\nAdding a head pointer\n");

head=temp;

tail=temp;

temp->value=value;
}

else

{

for(cur=head;cur->next!=NULL;cur=cur->next);

cur->next=temp;

temp->prev=cur;

temp->value=value;

tail=temp;
}
}

void print_list()

{

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

for(temp=head;temp!=NULL;temp=temp->next)

{

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

}
}

void reverse()

{

mynode *cur, *temp, *save_next;

if(head==tail)return;

if(head==NULL tail==NULL)return;

for(cur=head;cur!=NULL;)

{

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

temp=cur->next;

save_next=cur->next;

cur->next=cur->prev;

cur->prev=temp;

cur=save_next;

}
temp=head;

head=tail;

tail=temp;

}

Having shown all these different methods, if someone can mail me a really, really good practical application of reversing a linked list (singly or doubly linked list), I would be really thankful to them. I have not found one good application of this. All I see is an urge to understand how well the candidate handles the pointer manipulation