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

October 28, 2007 · Filed Under C Interview Questions, Placement Questions 



Don't want to miss a single bit? Subscribe By Email for Daily Jobs

Enter your email address :

All the latest from JobsAdda on Jobsadda.com delivered to your mailbox everyday.

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

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

// Variables
typedef 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

// Variables
typedef 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
#include

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.

Tags:

Related Articles


Get Latest JobsAdda.com Jobs, news & updates  via Email