Given a linked list, with all the nodes in sorted order. Write a function that inserts a new integer in the sorted manner. i.e If the list is as given below:
3 -> 6 -> 9 -> 10 -> 15
And if you want to insert 8 in this list, it should be inserted as below:
3 -> 6 -> 8 -> 9 -> 10 -> 15
Solution:
Let us assume that the LinkedList class is as given below:
class LinkedList { public: LinkedList(): head(NULL){}; LinkedList(int n) {}; void printList(); // Print the linked list void insertSorted(int n); // Insert in a sorted list private: Node* head; };
The structure of Node is as given below:
struct Node { int data; Node* link; // Constructor Node(int n):data(n), link(NULL) {} };
Ideally this Node should be a template and class LinkedList should also be a template, but our purpose is not a good design but writing just a function to insert in the sorted list.
The definition of insertSorted function is like shown below:
void LinkedList::insertSorted(int n) { Node *temp = NULL; // Inserting at the head of the list. if(head == NULL || head->data > n) { temp = new Node(n); temp->link = head; head = temp; return; } // Inserting anywhere else. temp = head; // Moving to the point where insertion need to be done. while( temp->link != NULL && temp->link->data < n ) { temp = temp->link; } Node *t = new Node(n); t->link = temp->link; temp->link = t; }
Please let me know your feedback / comments.