Linked list problems..............................................................

Sorted Insertion of a node into linked list. Solution...
Deletion of node from linked list. Solution...
Finding Nth element in a Linked List. Solution...
Binary search method. Solution...
Generate mirror image tree of given tree. Solution...

How about reversing the links in the existing linked list such that the last node becomes the first node and the first becomes the last? Here is a program which shows how this reversal of links can be achieved.

#include "alloc.h"

/* structure containing a data part and link part */

struct node

{

int data ;

struct node *link ;

} ;

reverse ( struct node ** ) ;

main( )

{

struct node *p ;

p = NULL ; /* empty linked list */

addatbeg ( &p, 1 ) ;

addatbeg ( &p, 2 ) ;

addatbeg ( &p, 3 ) ;

addatbeg ( &p, 4 ) ;

addatbeg ( &p, 5 ) ;

addatbeg ( &p, 6 ) ;

clrscr( ) ;

display ( p ) ;

printf ( "\nNo. of elements in the linked list = %d", count ( p ) ) ;

reverse ( &p ) ;

display ( p ) ;

printf ( "\nNo. of elements in the linked list = %d", count ( p ) ) ;

}

/* adds a new node at the beginning of the linked list */

addatbeg ( struct node **q, int num )

{

struct node *temp ;

/* add new node */

temp = malloc ( sizeof ( struct node ) ) ;

temp -> data = num ;

temp -> link = *q ;

*q = temp ;

}

reverse ( struct node **x )

{

struct node *q, *r, *s ;

q = *x ;

r = NULL ;

/* trasverse the entire linked list */

while ( q != NULL )

{

s = r ;

r = q ;

q = q -> link ;

r -> link = s ;

}

*x = r ;

}

/* displays the contents of the linked list */

display ( struct node *q )

{

printf ( "\n" ) ;

/* traverse the entire linked list */

while ( q != NULL )

{

printf ( "%d ", q -> data ) ;

q = q -> link ;

}

}

/* counts the number of nodes present in the linked list */

count ( struct node * q )

{

int c = 0 ;

/* traverse the entire linked list */

while ( q != NULL )

{

q = q -> link ;

c++ ;

}

return c ;

}

In reverse( ) two variables s and r of type struct node* play an important role for reversing the links of the existing linked list. The variable q also of type struct node* is used to traverse the linked list till the end. While traversing the linked list, r stores address of current node and s stores the address of the previous node. Subsequently, the link part of the node to which r points is assigned the value stored in s. Finally, the last node is made the head node as you see in the last statement in reverse( ).

Go Top