#include <bits/stdc++.h>
using namespace std;

class Node
{
    public:
	    int data;
	    Node *next;
	    Node(int data)
	    {
		    this->data = data;
		    this->next = NULL;
	    }
};

int calcLength(Node* head){
    int n=0;
    while(head){
        n++;
        head=head->next;
    }
    return n;
}

Node *bubbleSort(Node *head)
{
    // Write your code here
    if(head==NULL || head->next==NULL)
        return head;

    int n = calcLength(head);

    for(int i=0;i<n;i++){

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

        while(curr->next){

            if(curr->data > curr->next->data){

                if(prev==NULL){
                    Node* next = curr->next;
                    curr->next = next->next;
                    next->next = curr;

                    head = next;
                    prev = head ;
                }
                else{
                    Node* next = curr->next;
                    prev->next = next;
                    curr->next = next->next;
                    next->next = curr;

                    prev = next;
                }
            }
            else{
                prev=curr;
                curr=curr->next;
            }
        }
    }

    return head;

}

int main(){
    
    
    
}