Tuesday, December 9, 2008

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