在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。 样例： 给出 1->3->2->null，给它排序变成 1->2->3->null.
#ifndef C98_H #define C98_H #include<iostream> using namespace std; class ListNode{ public: int val; ListNode *next; ListNode(int val){ this->val = val; this->next = NULL; } }; class Solution { public: ListNode *sortList(ListNode *head) { if (!head || !head->next) return head; return mergeSort(head); } ListNode * mergeSort(ListNode *head){ if (!head || !head->next) return head; ListNode *p = head, *q = head, *pre = NULL; while (q&&q->next != NULL){ q = q->next->next; pre = p; p = p->next; } pre->next = NULL; ListNode *lhalf = mergeSort(head); ListNode *rhalf = mergeSort(p); return merge(lhalf, rhalf); } ListNode * merge(ListNode *lh, ListNode *rh){ ListNode *temp = new ListNode(0); ListNode *p = temp; while (lh&&rh){ if (lh->val <= rh->val){ p->next = lh; lh = lh->next; } else{ p->next = rh; rh = rh->next; } p = p->next; } if (!lh) p->next = rh; else p->next = lh; p = temp->next; temp->next = NULL; return p; } }; #endif