Jun 122012

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


Let us assume that the LinkedList class is as given below:

    class LinkedList
            LinkedList(): head(NULL){};
            LinkedList(int n) {};
            void printList();		 // Print the linked list
            void insertSorted(int n);	 // Insert in a sorted list

            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;

        // 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.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>