Question

Please use C++, linked list and Bubble Sort to slove this problem.

#include <iostream>
#include <time.h>

using namespace std;

struct ListNode {
int data;
ListNode *next;
ListNode(int x) : data(x), next(nullptr) {}
};

class LinkedList {

private:
ListNode *head = nullptr;
public:

void addNode(int x)
{
ListNode *p = new ListNode(x);
if (head == nullptr)

head = p;

else
{
ListNode *q = head;
while (q->next != nullptr)
q = q->next;
q->next = p;
}
}

void display()
{

ListNode *p = head;
if (p != nullptr)
{
while (p->next != nullptr)
{
cout << p->data << " -> ";
p = p->next;

}
cout << p->data << " @" << endl;
}
}

void sortList()

{

Please finish this part

}

int main()
{

LinkedList ll;
ll.addNode(23);
ll.addNode(91);
ll.addNode(2);
ll.addNode(21);
ll.addNode(2);
ll.addNode(36);
ll.addNode(42);
ll.addNode(12);
ll.addNode(30);
ll.addNode(19);
ll.sortList(); /// Implement the function

ll.display();
ll.deleteAll();

return 0;

}

Answer 1

The required code is added below followed by the output. The explanation of the complex code is added with the comment lines as well.

CODE:

#include <iostream>
#include <time.h>

using namespace std;

struct ListNode {
    int data;
    ListNode *next;
    ListNode(int x) : data(x), next(nullptr) {}
};


class LinkedList {

    private:
        ListNode *head = nullptr;
    public:

    void addNode(int x)
    {
        ListNode *p = new ListNode(x);
        if (head == nullptr)
            head = p;
        else
        {
            ListNode *q = head;
            while (q->next != nullptr)
                q = q->next;
            q->next = p;
        }
    }

    void display()
    {
        ListNode *p = head;
        if (p != nullptr)
        {
            while (p->next != nullptr)
            {
                cout << p->data << " -> ";
                p = p->next;
            }
        cout << p->data << " @" << endl;
        }
    }

    void sortList()

    {
        ListNode *q = head;              // INITIALIZED THE TRAVERSING POINTER WITH HEAD
        int n = 1;                       // N TO COUNT THE NUMBER OF ELEMENTS
        while (q->next != nullptr){
                q = q->next;
                n++;                     // INCREMENT N FOR EACH NEW POINTER
            }

        ListNode** curr;                  // A POINTER TO A POINTER OF NODE, WHICH WILL HELP IN SWAPPING

        for(int i=0;i<n;i++){              // PASS LOOP AS BUBBLE SORT

            curr = &head;                 // INITIALIZE WITH ADDRESS OF HEAD

            for(int j=0;j<n-i-1;j++){      // ANOTHER LOOP WHICH PLACES THE MAX ELEMENT INTO N-I'TH NODE

                ListNode* node1 = *curr;   // TWO NODE POINTERS FOR CURR AND NEXT
                ListNode* node2 = node1->next;


                if (node1->data > node2->data){  // IF DATA OF NODE 1 IS GREATER THAN 2 THEN SWAP ELSE DO NOTHING

                    ListNode* temp = node2->next;
                    node2->next = node1;
                    node1->next = temp;
                    *curr = node2;

                }
                curr = &(*curr)->next;          // INITIALIZE THE CURR WITH ADDRESS OF NEXT NODE.

            }

        }


    }

    void deleteAll(){
        ListNode *curr = head;
        while (curr != nullptr){
                ListNode* next = curr->next;
                delete curr;
                curr = next;
            }
        head = nullptr;
    }
};


int main()
{


    LinkedList ll;
    ll.addNode(23);
    ll.addNode(91);
    ll.addNode(2);
    ll.addNode(21);
    ll.addNode(2);
    ll.addNode(36);
    ll.addNode(42);
    ll.addNode(12);
    ll.addNode(30);
    ll.addNode(19);
    ll.sortList(); /// Implement the function



    ll.display();
    ll.deleteAll();
    return 0;

}

OUTPUT:

2 -> 2 -> 12 -> 19 -> 21 -> 23 -> 30 -> 36 -> 42 -> 91 @

NOTE: In case of any query, mention it in the comment section. HAPPY LEARNING!!