Answer to Question #233667 in C++ for Ahmad

Question

Write a SortedInsert() function which given a list that is sorted in increasing order, and a single
node, inserts the node into the correct sorted position in the list. Use Insert() function of task 1
allocates a new node to add to the list, SortedInsert() takes an existing node, and just rearranges
pointers to insert it into the list.

Answer 1

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




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




void printList(struct Node* head)
{
	struct Node* ptr = head;
	while (ptr)
	{
		printf("%d —> ", ptr->data);
		ptr = ptr->next;
	}


	printf("null");
}




void insert(struct Node** head, int data)
{
	struct Node* tempNode = (struct Node*)malloc(sizeof(struct Node));
	tempNode->data = data;
	tempNode->next = *head;
	*head = tempNode;
}




struct Node* new_node(int data)
{
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}




void sortedInsert(struct Node** head, struct Node* newNode)
{
	
	if (*head == NULL || (*head)->data >= newNode->data)
	{
		newNode->next = *head;
		*head = newNode;
		return;
	}


	
	struct Node* current = *head;
	while (current->next != NULL && current->next->data < newNode->data) {
		current = current->next;
	}


	newNode->next = current->next;
	current->next = newNode;
}


int main(void)
{
	
	int keys[] = {2, 4, 6, 8};
	int n = sizeof(keys)/sizeof(keys[0]);


	
	struct Node* head = NULL;




	for (int i = n-1; i >= 0; i--) {
		insert(&head, keys[i]);
	}


	sortedInsert(&head, new_node(5));
	sortedInsert(&head, new_node(9));
	sortedInsert(&head, new_node(1));


	
	printList(head);


	return 0;
}