Question

How to build sorted linear (singly) linked list and insert new items in sorted order with C++

Answer 1

#include <iostream>

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

void insert_sorted(struct Node** head, struct Node* new_node)
{
	struct Node* current;

	if (*head == NULL || (*head)->n >= new_node->n)
	{
		new_node->next = *head;
		*head = new_node;
	}
	else
	{
		current = *head;
		while (current->next != NULL && current->next->n < new_node->n)
			current = current->next;

		new_node->next = current->next;
		current->next = new_node;
	}
}

struct Node *create_node(int n)
{
	struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

	new_node->n = n;
	new_node->next = NULL;

	return new_node;
}

void print_linked_list(struct Node *head)
{
	struct Node *tmp = head;

	while (tmp != NULL)
	{
		std::cout << tmp->n << "  ";
		tmp = tmp->next;
	}
}

void free_linked_list(struct Node *head)
{
	struct Node *current = head;

	while (current)
	{
		current = current->next;
		free(head);
		head = current;
	}
}

int main()
{
	struct Node* head = NULL;
	struct Node *new_node = create_node(13);

	insert_sorted(&head, new_node);
	new_node = create_node(2);

	insert_sorted(&head, new_node);
	new_node = create_node(9);

	insert_sorted(&head, new_node);
	new_node = create_node(7);

	insert_sorted(&head, new_node);
	new_node = create_node(5);

	insert_sorted(&head, new_node);
	new_node = create_node(4);

	insert_sorted(&head, new_node);
	new_node = create_node(3);

	insert_sorted(&head, new_node);

	print_linked_list(head);

	free_linked_list(head);

	return 0;
}


/*
run:

2  3  4  5  7  9  13 

*/

 

70+ SQL courses for beginners and professionals