# Merge two sorted linked lists

QUESTION

Write a SortedMerge() function that takes two lists, each of which is sorted in increasing order, and merges the two together into one list which is in increasing order. SortedMerge() should return the new list. The new list should be made by splicing\ntogether the nodes of the first two lists.\n\nFor example if the first linked list a is 5->10->15 and the other linked list b is 2->3->20, then SortedMerge() should return a pointer to the head node of the merged list 2->3->5->10->15->20.\n\nThere are many cases to deal with: either a or b may be empty, during processing either a or b may run out first, and finally theres the problem of starting the result list empty, and building it up while going through a and b.

“TESTCASE_1”: “3 3\n5 10 15\n1 2 20\n###—###SEPERATOR—###—\n1 2 5 10 15 20”, “TESTCASE_2”: “5 4\n5 6 9 15 20\n2 4 8 10\n###—###SEPERATOR—###—\n2 4 5 6 8 9 10 15 20”, “TESTCASE_3”: “3 4\n5 6 9\n2 4 8 10\n###—###SEPERATOR—###—\n2 4 5 6 8 9 10”, “TESTCASE_4”: “7 4\n1 2 3 4 5 6 7\n2 4 8 10\n###—###SEPERATOR—###—\n1 2 2 3 4 4 5 6 7 8 10”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

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

struct Node
{
int data;
struct Node* next;
};

/* pull off the front node of the source and put it in dest */
void MoveNode(struct Node** destRef, struct Node** sourceRef);

/* Takes two lists sorted in increasing order, and splices
their nodes together to make one big sorted list which
is returned.  */
struct Node* SortedMerge(struct Node* a, struct Node* b)
{
/* a dummy first node to hang the result on */
struct Node dummy;

/* tail points to the last result node  */
struct Node* tail = &dummy;

/* so tail->next is the place to add new nodes
to the result. */
dummy.next = NULL;
while (1)
{
if (a == NULL)
{
/* if either list runs out, use the
other list */
tail->next = b;
break;
}
else if (b == NULL)
{
tail->next = a;
break;
}
if (a->data <= b->data)
MoveNode(&(tail->next), &a);
else
MoveNode(&(tail->next), &b);

tail = tail->next;
}
return(dummy.next);
}

/* UTILITY FUNCTIONS */
/* MoveNode() function takes the node from the front of the
source, and move it to the front of the dest.
It is an error to call this with the source list empty.

Before calling MoveNode():
source == {1, 2, 3}
dest == {1, 2, 3}

Affter calling MoveNode():
source == {2, 3}
dest == {1, 1, 2, 3} */
void MoveNode(struct Node** destRef, struct Node** sourceRef)
{
/* the front source node  */
struct Node* newNode = *sourceRef;
assert(newNode != NULL);

/* Advance the source pointer */
*sourceRef = newNode->next;

/* Link the old dest off the new node */
newNode->next = *destRef;

/* Move dest to point to the new node */
*destRef = newNode;
}

/* Function to insert a node at the beginging of the
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));

/* put in the data  */
new_node->data  = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

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

/* Drier program to test above functions*/
int main()
{
struct Node* res = NULL;
struct Node* a = NULL;
struct Node* b = NULL;
int n1,n2,i;
scanf("%d",&n1);
scanf("%d",&n2);
int a1[n1],a2[n2];
for(i=0;i<n1;i++)
scanf("%d",&a1[i]);
for(i=0;i<n2;i++)
scanf("%d",&a2[i]);
for(i=n1-1;i>=0;i--)
push(&a,a1[i]);
for(i=n2-1;i>=0;i--)
push(&b,a2[i]);

/* Let us create two sorted linked lists to test
the functions
Created lists, a: 5->10->15,  b: 2->3->20 */

/* Remove duplicates from linked list */
res = SortedMerge(a, b);

printList(res);

return 0;
}``````