2 40 pts Write a function that takes a linked list of intege

2. (40 pts Write a function that takes a linked list of integers and rearranges the nodes so that the integers stored are sorted into the order smallest to largest, with the smallest integer in the node at the head of the list. If the original list had any integers occurring more than once, then the changed list will have the same number of each integer. For concreteness you will use lists of integers, but your function should still work if you replace the integer type with any other type for which the less-than operation is part of a total order semantics. Use the following function prototype and specification void sort-kist (node & head-ptr); Precondition: head-ptr is a head pointer of a linked list of items, and these items can be compared with a less-than operator. //Postcondition: head-ptr points to the head of a linked list with exactly the same entries (including repetitions if any), but the entries in this list are sorted from smallest to largest. The original linked list is no longer available. Your procedure will implement the following algorithm (which is often called selection sort): The algorithm removes nodes one at a time from the original list and adds the nodes to a second list until all the nodes have been moved to the second list. The second list will then be sorted. Pseudo code for selection sort while (the first list still has some nodes.

Solution

#include<bits/stdc++.h> // please check if it works or not

using namespace std;

struct Node

{

    int data;

    struct Node *next;

};

Node *mergelist(Node *head1, Node *head2);

void splitList(Node *head, Node **Ahead, Node **Dhead);

void reverselist(Node *&head);

void sort_List(Node **head)

{

    // Split the list into lists

    Node *Ahead, *Dhead;

    splitList(*head, &Ahead, &Dhead);

    // Reverse the descending linked list

    reverselist(Dhead);

    // Merge the two linked lists

    *head = mergelist(Ahead, Dhead);

}

// A utility function to create a new node

Node* newNode(int key)

{

    Node *temp = new Node;

    temp->data = key;

    temp->next = NULL;

    return temp;

}

// A utility function to reverse a linked list

void reverselist(Node *&head)

{

    Node* prev = NULL, *curr = head, *next;

    while (curr)

    {

        next = curr->next;

        curr->next = prev;

        prev = curr;

        curr = next;

    }

    head = prev;

}

// A utility function to print a linked list

void printlist(Node *head)

{

    while (head != NULL)

    {

        cout << head->data << \" \";

        head = head->next;

    }

    cout << endl;

}

Node *mergelist(Node *head1, Node *head2)

{

    // Base cases

    if (!head1) return head2;

    if (!head2) return head1;

    Node *temp = NULL;

    if (head1->data < head2->data)

    {

        temp = head1;

        head1->next = mergelist(head1->next, head2);

    }

    else

    {

        temp = head2;

        head2->next = mergelist(head1, head2->next);

    }

    return temp;

}

void splitList(Node *head, Node **Ahead, Node **Dhead)

{

    // Create two dummy nodes to initialize heads of two linked list

    *Ahead = newNode(0);

    *Dhead = newNode(0);

    Node *ascn = *Ahead;

    Node *dscn = *Dhead;

    Node *curr = head;

    while (curr)

    {

        

        ascn->next = curr;

        ascn = ascn->next;

        curr = curr->next;

        if (curr)

        {

            dscn->next = curr;

            dscn = dscn->next;

            curr = curr->next;

        }

    }

    ascn->next = NULL;

    dscn->next = NULL;

    *Ahead = (*Ahead)->next;

    *Dhead = (*Dhead)->next;

}

int main()

{

    Node *head = newNode(10);

    head->next = newNode(40);

    head->next->next = newNode(53);

    head->next->next->next = newNode(30);

    head->next->next->next->next = newNode(67);

    head->next->next->next->next->next = newNode(12);

    head->next->next->next->next->next->next = newNode(89);

    cout << \"Given Linked List is \" << endl;

    printlist(head);

    sort_List(&head);

    cout << \"Sorted Linked List is \" << endl;

    printlist(head);

    return 0;

}