Linked Lists 4

Suppose we have two linked lists pointed to by two independent pointers and we wish to merge the two lists into a third list. While carrying out this merging we wish to ensure that those elements which are common to both the lists occur only once in the third list. The program to achieve this is given below. It is assumed that within a list all elements are unique.

#include "alloc.h"

struct node

{

int data ;

struct node *link ;

} ;

main( )

{

struct node *first, *second, *third ;

first = second = third = NULL ; /* empty linked lists */

add ( &first, 1 ) ;

add ( &first, 2 ) ;

add ( &first, 3 ) ;

add ( &first, 4 ) ;

add ( &first, 5 ) ;

add ( &first, 6 ) ;

add ( &first, 7 ) ;

clrscr( ) ;

printf ( "First linked list : " ) ;

display ( first ) ;

printf ( "\nNo. of elements in Linked List : %d" , count ( first ) ) ;

add ( &second, 8 ) ;

add ( &second, 9 ) ;

add ( &second, 3 ) ;

add ( &second, 4 ) ;

add ( &second, 5 ) ;

add ( &second, 6 ) ;

add ( &second, 7 ) ;

printf ( "\n\nSecond linked list : " ) ;

display ( second ) ;

printf ( "\nNo. of elements in Linked List : %d" , count ( second ) ) ;

merge ( first, second, &third ) ;

printf ( "\n\nThe concatenated list : " ) ;

display ( third ) ;

printf ( "\nNo. of elements in Linked List : %d", count ( third ) ) ;

}

/* adds node to an ascending order linked list */

add ( struct node **q, int num )

{

struct node *r, *temp = *q ;

r = malloc ( sizeof ( struct node ) ) ;

r -> data = num ;

/* if list is empty or if new node is to be inserted before the first node */

if ( *q == NULL || ( *q ) -> data > num )

{

*q = r ;

( *q ) -> link = temp ;

}

else

{

/* traverse the entire linked list to search the position to insert the new node */

while ( temp != NULL )

{

if ( temp -> data < num && ( temp -> link -> data > num

|| temp -> link == NULL ) )

{

r -> link = temp -> link ;

temp -> link = r ;

return ;

}

temp = temp -> link ; /*go to next node */

}

r -> link = NULL ;

temp -> link = 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 ;

}

/* merges the two linked lists, restricting the common elements to occur only once in the final list */

merge ( struct node *p, struct node *q, struct node **s )

{

struct node *z ;

z = NULL ;

if ( p == NULL && q == NULL )

return ;

while ( p != NULL && q != NULL )

{

if ( *s == NULL )

{

*s = malloc ( sizeof ( struct node ) ) ;

z = *s ;

}

else

{

z -> link = malloc ( sizeof ( struct node ) ) ;

z = z -> link ;

}

if ( p -> data < q -> data )

{

z -> data = p -> data ;

p = p -> link ;

}

else

{

if ( q -> data < p -> data )

{

z -> data = q -> data ;

q = q -> link ;

}

else

{

if ( p -> data == q -> data )

{

z -> data = q -> data ;

p = p -> link ;

q = q -> link ;

}

}

}

}

while ( p != NULL )

{

z -> link = malloc ( sizeof ( struct node ) ) ;

z = z -> link ;

z -> data = p -> data ;

p = p -> link ;

}

while ( q != NULL )

{

z -> link = malloc ( sizeof ( struct node ) ) ;

z = z -> link ;

z -> data = q -> data ;

q = q -> link ;

}

z -> link = NULL ;

}

In this program as usual we begin by building a structure to accommodate the data and link which together represent a node. We have used pointers first, second and third to point to the three linked lists. Since to begin with all the three linked lists are empty, these pointers contain NULL. Next, by calling the function add( ) repeatedly two linked lists are built, one being pointed to by first and other by the pointer second. Finally, the merge( ) function is called to merge the two lists into one. This merged list is pointed to by the pointer third. While merging the two lists it is assumed that the lists themselves are in ascending order. While building the two lists the add( ) function makes sure that when a node is added the elements in the lists are maintained in ascending order. While merging the two lists, the merge( ) function accounts for the possibility of any of the two lists being empty.