/**

Definition for singlylinked list.

struct ListNode {

int val;

ListNode *next;

ListNode(int x) : val(x), next(NULL) {}

};
/
class Solution {
public:
ListNode sortList(ListNode* head) {if(head == NULL) { return head; } ListNode *h = head; ListNode *p = head>next; if(p == NULL){ return head; } ListNode *Btemp = NULL; ListNode *bt=NULL; ListNode *Atemp = NULL; ListNode *at=NULL; while(p){ if(p>val < head>val){ if(Btemp){ bt>next = p; bt = bt>next; } else{ Btemp = p; bt = Btemp; } }else if(p>val > head>val){ if(Atemp){ at>next = p; at = at>next; } else{ Atemp = p; at = Atemp; } }else{ h>next = p; h = h>next; } p= p>next; } if(bt){ bt>next = NULL; } if(at){ at>next = NULL; } bt = sortList(Btemp); at = sortList(Atemp); h>next = at; if(bt){ ListNode *bl = bt; while(bl>next){ bl = bl>next; } bl>next = head; }else{ bt = head; } return bt;
}
};