THIS PROGRAM SHOULD BE DONE IN C Programming Language! (4) Merge You\'re given t

Question

THIS PROGRAM SHOULD BE DONE IN C Programming Language!

(4) Merge You're given the pointer to the head nodes of two sorted linked lists. The data in both lists will be sorted in ascending order. Change the next pointers to obtain a single, merged linked list which also has data sorted in ascending order. Either head pointer given may be null meaning that the corresponding list is empty Input Format You have to complete the Node* MergeLists (Node* headA, Node* headB) function which takes two arguments the heads of the two sorted linked lists to merge. Read input from console to first create the sorted linked lists A and B. The first line of input is the number of test cases. For each test case, there are two lines of input strings representing list A and B Output Format Change the next pointer of individual nodes so that nodes from both lists are merged into a single list. Then return the head of this merged list. Write a print() function to print the final sorted list to the console Sample Input 1->3->5->6-NULL 15 -NULL 12-NULL NULL 1->2->NULL Sample Output 1->2->3-4-5-6- 12-> 15 .> NULL 1->2->NULL 7-NULL

Explanation / Answer

Solution for above problem is:

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

/* Link list node */
struct ListNode {
int val;
struct ListNode *next;
};

typedef struct ListNode listnode;

listnode* listnode_new(int val) {
listnode* node = (listnode *) malloc(sizeof(listnode));
node->val = val;
node->next = NULL;
return node;
}

listnode* MergLists(listnode* A, listnode* B) {
listnode *ans,*ptr1=A,*ptr2=B;
if(A==NULL) return B;
if(B==NULL) return A;
if(A->val<B->val)
{
ans=A;
ptr1=ptr1->next;
}
else
{
ans=B;
ptr2=ptr2->next;
}
while(ptr1 && ptr2)
{
if(ptr1->val<ptr2->val)
{
ans->next=ptr1;
ans=ptr1;
ptr1=ptr1->next;
}
else
{
ans->next=ptr2;
ans=ptr2;
ptr2=ptr2->next;
}
}
if(ptr2)
ans->next=ptr2;
else
ans->next=ptr1;
if(A->val<B->val) return A;
else return B;
}

void push(struct ListNode** head_ref, int new_data)
{

struct ListNode* new_node =
(struct ListNode*) malloc(sizeof(struct ListNode));

new_node->val = new_data;

new_node->next = (*head_ref);

  
(*head_ref) = new_node;
}

/* Function to print nodes in a given linked list */
void printList(struct ListNode *node)
{
while (node!=NULL)
{
printf("%d ", node->val);
node = node->next;
}
}

int main()
{
  
struct Node* res = NULL;
struct Node* a = NULL;
struct Node* b = NULL;

  
int i=0,j=0,k=0,n=0, l=0, m=0, x=0, y=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("How many element in list a:");
scanf("%d",&l);
for(j=1;j<=l;j++){
x =0;
scanf("%d",&x);
push(&a, x);
}
printList(a);
printf("How many element in list b:");
scanf("%d",&m);
for(k=1;k<=m;k++){
y=0;
scanf("%d",&y);
push(&a, y);
}
printList(b);
res = MergLists(a, b);
}
printf("Merged Linked List is: ");
printList(res);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.