Answer to Question #236733 in C++ for Volkner

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 <iostream>
using namespace std;


struct Node {
    double val;
    struct Node* next;
    Node(double x)
    {
        val = x;
        next = NULL;
    }
};

class Linkedlist {
public:
    Node* head;
    Node* sorted;
    //add node
    void push(double val)
    {
        Node* newnode = new Node(val);
        newnode->next = head;
        head = newnode;
    }
    // insert a new  node in a list
    void  Insert(Node* newnode)
    {
        if (sorted == NULL || sorted->val >= newnode->val) {
            newnode->next = sorted;
            sorted = newnode;
        }
        else {
            Node* current = sorted;
            while (current->next != NULL
                && current->next->val < newnode->val) {
                current = current->next;
            }
            newnode->next = current->next;
            current->next = newnode;
        }
    }
    // sorted list 
    void SortedInsert(Node* headref)
    {
        sorted = NULL;
        Node* current = headref;
        while (current != NULL) {
            Node* next = current->next;
            Insert(current);
            current = next;
        }
        head = sorted;
    }
    //list output
    void printlist(Node* head)
    {
        while (head != NULL) {
            cout << head->val << " ";
            head = head->next;
        }
    }
};


int main()
{


    Linkedlist example;
    // initial linked list
   example.head = NULL;
   double values[6] = { 1.2, 5.8, 2.4, 3,7.8, 6 };
   for (int i = 0; i < 6; i++) 
   {
       example.push(values[i]);
   }
    cout << "Linked List " << endl;
    example.printlist(example.head);
    cout << endl;
    example.SortedInsert(example.head);
    cout << "Linked List sorted" << endl;
    example.printlist(example.head);
    return 0;
}