Answer to Question #266043 in C++ for zxc

Question

Write a non-member function that shuffle-merge the nodes of

the two linked lists (list1 and list2) to First list, by taking nodes

alternately from the two lists such that the resultant list contains

distinct elements. Both lists contain unique elements each but can

have common elements. For example, if list1 contains {1 3 5 7}

and list2 contains {11 12 5 13 14}, then after the function call

shuffleMerge(list1,list2), list1 should contain

{1->11->3->12->5->13->7->14} and list2 should be empty now.

Note: You are NOT allowed to create any new node in this

function.

Answer 1

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
struct Node
{
	int d;
	struct Node* nxt;
};


void MoveNode(struct Node** destRef, struct Node** sourceRef);


struct Node* SortedMerge(struct Node* a, struct Node* b)
{
	struct Node dummy;
	struct Node* tail = &dummy;
	dummy.nxt = NULL;
	while (1)
	{
		if (a == NULL)
		{
			tail->nxt = b;
			break;
		}
		else if (b == NULL)
		{
			tail->nxt = a;
			break;
		}
		if (a->d <= b->d)
			MoveNode(&(tail->nxt), &a);
		else
			MoveNode(&(tail->nxt), &b);


		tail = tail->nxt;
	}
	return(dummy.nxt);
}
void MoveNode(struct Node** dRef, struct Node** sRef)
{
	struct Node* newNode = *sRef;
	assert(newNode != NULL);
	*sRef = newNode->nxt;
	newNode->nxt = *dRef;
	*dRef = newNode;
}


void push(struct Node** h_ref, int n_data)
{
	struct Node* n_node =
		(struct Node*) malloc(sizeof(struct Node));
	n_node->d = n_data;
	n_node->nxt = (*h_ref);
	(*h_ref) = n_node;
}
void display(struct Node *nd)
{
	while (nd!=NULL)
	{
		printf("%d ", nd->d);
		nd = nd->nxt;
	}
}
int main()
{
	struct Node* result = NULL;
	struct Node* x = NULL;
	struct Node* y = NULL;
	push(&x, 15);
	push(&x, 10);
	push(&x, 5);


	push(&y, 20);
	push(&y, 3);
	push(&y, 2);
	result = SortedMerge(x,y);


	printf("Merged Linked List is: \n");
	display(result);


	return 0;
}