Question

Due to a rush at the end of the exam, Professor could not arrange the answer sheets in the

sequence as desired. However, he mentioned the correct location of each answer sheet with it.

Now, Professor wants all the answer sheets in the desired sequence.prepare a linklist having a data, the location, and the link node to arrange the data in the in the increasing manner of the location variable.

HINT: Item ,location ,linknode

input: 5 3 ->6 2 ->4 1->2 4 NULL

output: 4 1->6 2->5 3->2 4 NULL

Answer 1

#include <bits/stdc++.h>
using namespace std;


class Node {
public:
	int d;
	Node* nt;
};




void insert(Node** h_ref, Node* new_node)
{
	Node* cur;
	if (*h_ref == NULL
		|| (*h_ref)->d
			>= new_node->d) {
		new_node->nt = *h_ref;
		*h_ref = new_node;
	}
	else {
		cur = *h_ref;
		while (cur->nt != NULL
&& cur->nt->d
< new_node->d) {
			cur = cur->nt;
		}
		new_node->nt = cur->nt;
		cur->nt = new_node;
	}
}


Node* newNode(int new_data)
{
	Node* new_node = new Node();
	new_node->d = new_data;
	new_node->nt = NULL;


	return new_node;
}


void print(Node* h)
{
	Node* temp = h;
	while (temp != NULL) {
		cout << temp->d << " ";
		temp = temp->nt;
	}
}


int main()
{
	Node* h = NULL;
	Node* new_n = newNode(4);
	insert(&h, new_n);
	new_n = newNode(14);
	insert(&h, new_n);
	new_n = newNode(12);
	insert(&h, new_n);
	new_n = newNode(15);
	insert(&h, new_n);
	new_n = newNode(17);
	insert(&h, new_n);
	
	print(h);


	return 0;
}