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)
Method2 (Recursive, without using any temporary variable)
#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");
}
#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
#includetypedef 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.
Re: How do you reverse a singly linked list? How do you reverse
thank you very much to you
Re: How do you reverse a singly linked list? How do you reverse
class Node { private: int data; class Node *next; public: static Node *head; static Node *tail; Node(int i) : data(i) { next = NULL; } ~Node() { cout << "Destructing. . ." << data << endl; } static void assign_head(Node *nd) { head = nd; } static void assign_tail(Node *nd) { tail = nd; } void add_to_list(void); static void print_list(void); static Node* reverse_list(Node *, Node*); static void destroy_list(void); };// rev_sll.cpp // Author: Satish M S // Nov 04, 2007 // Reverse Singly List Recursively#include
#include
#include "rev_sll.h"
#define SOME_NUMBER 15
Node* Node::head = NULL;
Node* Node::tail = NULL;
int main() {
int i;
Node *node;
for (i = 1; i <= SOME_NUMBER; i++) {
node = new Node(i);
node->add_to_list();
}
Node::print_list();
system("PAUSE");
(void) Node::reverse_list(Node::head, NULL);
Node::print_list();
Node::destroy_list();
system("PAUSE");
return 0;
}
void Node::add_to_list (void) {
if (!head)
head = tail = this;
else {
tail->next = this;
tail = this;
}
}
Node* Node::reverse_list(Node* node, Node* pr) {
if (!node) {
cout << "Begin Unwinding . . ." << endl << endl;
return NULL;
}
(void) Node::reverse_list((node->next), node);
if (node->next == NULL)
Node::assign_head(node);
node->next = pr;
if (!pr)
Node::assign_tail(node);
return node;
}
void Node::print_list(void) {
Node *s_node = Node::head;
cout << "print_list . . ." << endl;
while (s_node) {
cout << s_node->data << endl;
s_node = s_node->next;
}
}
void Node::destroy_list(void) {
Node *s_node = Node::head;
Node *temp = NULL;
cout << "Destroy List . . ." << endl;
while (1) {
temp = s_node;
s_node = s_node->next;
delete temp;
temp = NULL;
if (s_node == NULL) break;
}
s_node = NULL;
}
Re: How do you reverse a singly linked list? How do you reverse
Thank you very much. Exactly what i was looking for.
program
u tried very well but i hope u can make it a bit easier so that even normal people can understand..its just a suggestion ur creativity is good thanx 4 giving programs