Sort a linked list in O(n log n) time using constant space complexity.

 法I：快排。快排的难点在于切分序列。从头扫描，碰到>=target的元素，停止；从第二个字串扫描，碰到<=target的元素停止；交换这两个元素。这样的好处是：当数据元素都相同时，也能控制在logn次递归（否则需要O(n))。另外，要注意避免子序列只剩两个相等元素时的死循环。

/** * 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 || head->next==NULL) return head; //only one element                ListNode* dummyHead1 = new ListNode(0);        ListNode* dummyHead2 = new ListNode(0);        ListNode* fastNode = dummyHead1;        ListNode* slowNode = dummyHead1;        ListNode* cur1, *cur2;        int tmp;        dummyHead1->next = head;                //fast, slow pointer to find the middle point        while(fastNode->next){            fastNode = fastNode->next;            if(fastNode->next) fastNode = fastNode->next;            else break;            slowNode = slowNode->next; //slowNode always point to the element before center(odd number)                                      // or the left center (even number)        }            //partition the sequence into two halves        dummyHead2->next = slowNode->next;        slowNode->next=NULL;        cur1 = dummyHead1;         cur2 = dummyHead2->next;        while(cur1->next&&cur2->next){           //stop when find an element in first half, value of whihch >= target           while(cur1->next && cur1->next->val < dummyHead2->next->val) cur1 = cur1->next;           //stop when find an element in second half,  value of which <= target           while(cur2->next && cur2->next->val > dummyHead2->next->val) cur2 = cur2->next;           if(!cur1->next || !cur2->next ) break;           tmp = cur1->next->val;           cur1->next->val = cur2->next->val;           cur2->next->val = tmp;           cur1 = cur1->next;           cur2 = cur2->next;                   }        while(cur1->next){            //stop when find an element in first half, value of which > target            //>= may lead to endless recursion if two equal elements left            while(cur1->next && cur1->next->val <= dummyHead2->next->val) cur1 = cur1->next;            if(!cur1->next) break;            cur2->next = cur1->next;            cur1->next = cur1->next->next;            cur2 = cur2->next;            cur2->next = NULL;        }        while(cur2->next){            //stop when find an element in second half, value of which < target            //<= may lead to endless recursion if two equal elements left            while(cur2->next && cur2->next->val >= dummyHead2->next->val) cur2 = cur2->next;            if(!cur2->next) break;            cur1->next = cur2->next;            cur2->next = cur2->next->next;            cur1 = cur1->next;            cur1->next = NULL;        }                //cascade two halves        head = sortList(dummyHead1->next);        cur2 = sortList(dummyHead2->next);        if(head==NULL) return cur2;        cur1 = head;        while(cur1->next){            cur1 = cur1->next;        }         cur1->next = cur2;        return head;    }};

 法II: 归并排序。由于是List，归并排序的好处是不用额外申请O(n)的空间

/** * 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 || head->next==NULL) return head; //only one element                ListNode* dummyHead1 = new ListNode(0);        ListNode* dummyHead2 = new ListNode(0);        ListNode* fastNode = dummyHead1;        ListNode* slowNode = dummyHead1;        ListNode* cur1, *cur2, *cur;        dummyHead1->next = head;                //fast, slow pointer to find the middle point        while(fastNode->next){            fastNode = fastNode->next;            if(fastNode->next) fastNode = fastNode->next;            else break;            slowNode = slowNode->next; //slowNode always point to the element before center(odd number)                                      // or the left center (even number)        }        dummyHead2->next = slowNode->next;        slowNode->next = NULL;                //recursion        cur1 = sortList(dummyHead1->next);        cur2 = sortList(dummyHead2->next);                //merge        cur = dummyHead1;        while(cur1 && cur2){            if(cur1->val <= cur2->val){                cur->next = cur1;                cur1 = cur1->next;            }            else{                cur->next = cur2;                cur2 = cur2->next;            }            cur = cur->next;        }        if(cur1){            cur->next = cur1;        }        else{            cur->next = cur2;        }        return dummyHead1->next;    }};