Question

With C++,

1. Assume we use two linked lists that represent Set A and Set B respectively. Implement the
following function to calculate A = A U B. Note that a SET should not contain duplicated
elements (e.g., integers).

void unionLL (Node * LA, Node * LB);

2. There are two linked lists, LA and LB. Their elements are both in the non-descending order.
Implement the following function to merge LA and LB into a new linked list, LC. Make sure that
the elements in LC are still in the non-descending order. (50 Points)

void mergeLL (Node * LA, Node * LB, Node * LC);

Example:
LA = (3, 5, 8, 11)
LB = (2, 6, 8, 9, 22, 24)
Then:
LC = (2, 3, 5, 6, 8, 8, 9, 11, 22, 24)

Additional requirements:
1. Create a main function and print out the numbers in the linked lists before and after
executing each method above.

2. Assume Node is defined as follows:
struct Node{
int num;
Node * next;
};

Any help appreciated.

Answer 1

1. code:

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

struct Node
{
int num;
struct Node *next;
};
void append (struct Node **L_head, int x);

bool isPresent (struct Node *head, int num);

void printList (struct Node *node);

void unionLL (Node * LA, Node * LB)
{
struct Node *t1 = LA;
struct Node *t2 = LB;
struct Node *t3 = NULL;
while (t1 != NULL)
{
append (&t3, t1->num);
t1 = t1->next;
}
while (t2 != NULL)
{
if (!isPresent (t3, t2->num))
   append (&t3, t2->num);

t2 = t2->next;
}
printf ("\nUnion of A and B is:\n");
printList (t3);
}

void append (struct Node **L_head, int x)
{
struct Node *new_node = (struct Node *) malloc (sizeof (struct Node));
struct Node *last = (*L_head);

new_node->num = x;
new_node->next = NULL;
if (*L_head == NULL)
{
*L_head = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
}

void printList (struct Node *node)
{
while (node != NULL)
{
printf ("%d ", node->num);
node = node->next;
}
}

bool isPresent (struct Node *head, int num)
{
struct Node *t = head;
while (t != NULL)
{
if (t->num == num)
   return 1;
t = t->next;
}
return 0;
}

int main ()
{
struct Node *LA = NULL;
struct Node *LB = NULL;
struct Node *mergeL = NULL;
append (&LA, 3);
append (&LA, 5);
append (&LA, 8);
append (&LA, 11);
append (&LB, 2);
append (&LB, 6);
append (&LB, 8);
append (&LB, 9);
append (&LB, 22);
append (&LB, 24);
printf ("\nA is:\n");
printList (LA);
printf ("\nB is:\n");
printList (LB);

unionLL (LA, LB);
return 0;
}
output: