BubbleSortRecursiveLinkedList.cpp

#include <iostream>

using namespace std;

//Blueprint for our NODE
class Node{
public:
    int data;
    Node* next;
    // ctor1
    Node(int d){
        data = d;
        next = NULL;
    }
};

//Create list
Node* createLL(int n){
    Node* head = NULL;
    Node* tail = NULL;
    
    while(n!=0){
        int x;
        cin >> x;
        
        Node* curNode = new Node(x);
        if (head == NULL){
            // curNode is the first node of our list
            head = curNode;
            tail = curNode;
        }
        else{
            tail->next = curNode;
            tail = tail->next;
        }
        
        n--;
    }
    return head;
}

//display
void display(Node* head){
    Node* cur = head;
    while(cur != NULL){                 // while(cur)
        cout << cur->data << " ";
        cur = cur->next;
    }
}

Node* BubbleSort(Node* &head, int n)
{
    Node* cur = head;
    
    if(n==1) // size of list is one
        return head;
        
    // recursive function
    
    
            Node* prev = cur;
    int i = 0;
            while(cur&&cur->next && i!=n)
            {
                Node* ahead = cur->next;
                if(cur->data > ahead->data)
                {
                    if(cur == head)
                    {
                        head = ahead;
                        cur->next = ahead->next;
                        ahead->next = cur;
                        prev = head;
                    }
                    else
                    {
                        prev->next = ahead;
                        cur->next = ahead->next;
                        ahead->next = cur;
                        prev = ahead;
                    }
                }
                
                else
                {
                    prev = cur;
                    cur = cur->next;
                }
                
                i++;
            }
    
    return BubbleSort(head, n-1);
}

int main()
{
    int n;
    cin>>n;
    
    Node* head = createLL(n);
    
    BubbleSort(head, n);
    
    display(head);
}