Implement a program to sort the elements in a single link list.
Problem : Implement a program to sort the elements in a single link list.
#include <bits/stdc++.h>
#include<conio.h>
using namespace std;
class Node {
public:
int data;
Node* next;
};
void sortedInsert(Node** head_ref,Node* new_node)
{
Node* current;
/* Special case for the head end */
if (*head_ref == NULL
|| (*head_ref)->data
>= new_node->data) {
new_node->next = *head_ref;
*head_ref = new_node;
}
else {
/* Locate the node before the
point of insertion */
current = *head_ref;
while (current->next != NULL && current->next->data< new_node->data)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
Node* newNode(int new_data)
{
/* allocate node */
Node* new_node = new Node();
/* put in the data */
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}
/* Function to print linked list */
void displayMethod(Node* head)
{
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
/* Driver program to test count function*/
int main()
{
/* Start with the empty list */
Node* head = NULL;
Node* new_node = newNode(10);
sortedInsert(&head, new_node);
new_node = newNode(85);
sortedInsert(&head, new_node);
new_node = newNode(25);
sortedInsert(&head, new_node);
new_node = newNode(45);
sortedInsert(&head, new_node);
new_node = newNode(15);
sortedInsert(&head, new_node);
cout << "\nYour sorted link list is:";
displayMethod(head);
getch();
return 0;
}
No comments