/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        ListNode* p = head;
        int len = 0;
        //先计算出链表的长度
        while(p){
            len++;
            p = p->next;
        }
        //进行冒泡排序
        for(int i=0;i<len-1;i++){
            ListNode* q = head;
            for(int j=0;j<len-i-1;j++){
                if((q->val) > (q->next->val)){
                    int temp = q->val;
                    q->val = q->next->val;
                    q->next->val = temp;
                }
                q = q->next;
            }
        }
        return head;
    }
};