/** * Definition for singly-linked 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 NULL;        if(head->next == NULL)            return head;                    ListNode* middle = head,*middlecur = middle;                ListNode* littlehead = NULL,*littlecur = NULL;        ListNode* bighead = NULL,*bigcur = NULL;        ListNode* cur = middle->next;                while(cur != NULL)        {            if(cur->val < middle->val)            {                if(littlehead == NULL)				{                    littlehead = cur;					littlecur = cur;				}                else				{                    littlecur->next = cur;					littlecur = littlecur->next;				}            }            else if(cur->val > middle->val)            {                if(bighead == NULL)				{                    bighead = cur;					bigcur = cur;				}                else				{                    bigcur->next = cur;					bigcur = bigcur->next;				}            }            else             {                middlecur->next = cur;                middlecur = middlecur->next;            }            cur = cur->next;        }        if(littlecur != NULL)            littlecur->next = NULL;        if(bigcur != NULL)            bigcur->next = NULL;                ListNode* rel = sortList(littlehead);        cur = rel;        ListNode* reb = sortList(bighead);        middlecur->next = reb;        if(rel == NULL)            return middle;        else        {            while(cur->next != NULL)                cur = cur->next;            cur->next = middle;            return rel;        }    }};

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode *sortList(ListNode *head) {        //quick sort???        return sortList_ht(head).first;    }    //head && tail    pair<ListNode*,ListNode*> sortList_ht(ListNode *head) {        if(head == NULL)            return pair<ListNode*,ListNode*>(NULL,NULL);        if(head->next == NULL)            return pair<ListNode*,ListNode*>(head,head);        ListNode *partition_b = head,*partition_e = head;        ListNode *cur = head->next;        ListNode *hs = NULL,*hb = NULL,*ts = NULL,*tb = NULL;        while(cur != NULL) {            if(cur->val < partition_b->val) {                if(hs == NULL) {                    hs = cur;                    ts = cur;                }                else {                    ts->next = cur;                    ts = ts->next;                }            }            else if(cur->val > partition_b->val) {                if(hb == NULL) {                    hb = cur;                    tb = cur;                }                else {                    tb->next = cur;                    tb = tb->next;                }            }            else {                partition_e->next = cur;                partition_e = partition_e->next;            }            cur = cur->next;        }        if(ts != NULL)            ts->next = NULL;        if(tb != NULL)            tb->next = NULL;        pair<ListNode*,ListNode*> ps = sortList_ht(hs);        pair<ListNode*,ListNode*> pb = sortList_ht(hb);        ListNode *rh,*rt;        if(ps.second == NULL) {            rh = partition_b;        }        else {            rh = ps.first;            ps.second->next = partition_b;        }        if(pb.first == NULL) {            rt = partition_e;            partition_e->next = NULL;        }        else {            rt = pb.second;            partition_e->next = pb.first;        }        return pair<ListNode*,ListNode*>(rh,rt);    }};