Advanced Operations on Linked Lists Implement a function that merges (in other w
ID: 3857597 • Letter: A
Question
Advanced Operations on Linked Lists Implement a function that merges (in other words puts them together) two sorted linked lists so that the new list is also sorted. It takes as an argument the head of two lists that are already sorted from smallest to largest. Then, it returns the new head for the joint list that is also sorted from smallest to largest. From the new head it should be possible to reach all other nodes i in the combined list. typedef struct node { int data: struct node *next: } List: List * sorted_merge (List * a, List * b);Explanation / Answer
Below is a working c program for this. Let me know if you have any concern in comments.
#include<stdio.h>
typedef struct node {
int data;
struct node*next;
}List;
List* sorted_merge(List *headA, List* headB)
{
if (headA == NULL && headB == NULL) {
return NULL;
}
if (headA == NULL) {
return headB;
}
if (headB == NULL) {
return headA;
}
// Ensure that list A starts with the smaller number
if (headA->data > headB->data) {
List *tmp = headB;
headB = headA;
headA = tmp;
}
List *listHead = headA;
while (headB) {
// Advance through nodes in list A until the next node
// has data bigger than data at current node of list B
while (headA->next != NULL &&
headB->data > headA->next->data) {
headA = headA->next;
}
// Insert current node in list B into list A
List* nextB = headB->next;
headB->next = headA->next;
headA->next = headB;
headB = nextB;
}
return listHead;
}
List l1[] = {
{ 1, &l1[1] },
{ 3, &l1[2] },
{ 5, &l1[3] },
{ 7, &l1[4] },
{ 9, &l1[5] },
{11, 0 },
};
List l2[] = {
{ 2, &l2[1] },
{ 4, &l2[2] },
{ 6, 0 },
};
void main() {
printf(" List 1 : ");
List *t1 = l1;
while( t1 != NULL) {
printf("%d ", t1->data);
t1 = t1->next;
}
printf(" List 2 : ");
List *t2 = l2;
while( t2 != NULL) {
printf("%d ", t2->data);
t2 = t2->next;
}
printf(" Merged List : ");
List *t = sorted_merge(l1, l2);
while( t != NULL) {
printf("%d ", t->data);
t = t->next;
}
return 0;
}
Sample Run: -
List 1 : 1 3 5 7 9 11
List 2 : 2 4 6
Merged List : 1 2 3 4 5 6 7 9 11
--------------------------------
Process exited after 0.1235 seconds with return value 0
Press any key to continue . . .
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.