问题描述 :
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3 输出: 1->2->3->4
示例 2: 输入: -1->5->3->4->0 输出: -1->0->3->4->5
输入范例： 5 -1 5 3 4 0
输出范例： head–>-1–>0–>3–>4–>5–>tail
思路： 1、O（nlogn）的时间复杂度： 常用的冒泡排序、选择排序、插入排序的时间复杂度为O (n^2)，不满足要求。快速排序平均时间复杂度为O(n logn)，最差为O(n^2)，也不合适。 归并排序的时间复杂度为O(n log n)，满足要求 2、O（1）的空间复杂度： 数组下的归并排序为O(n)，即建立一个数组来存放排好的数。 但在链表数据结构下，空间复杂度为O(1)。 因为链表的节点从一开始给定后就不在变更，在排序过程中只是每个节点指向位置不同，即指针变化，而节点数不变。 3、通过上述分析，用归并排序解题。 即为归并排序在链表中的应用。 从head结点往后撸，找到中间结点并把链表一分为二，递归此步骤。 设置快指针fast和慢指针slow，fast跑两步slow跑一步，当fast跑的最后一个节点时，slow到达middle处。递归上述步骤，归并时将结点重新排列。
#include<iostream> using namespace std; struct ListNode{ int val; struct ListNode *next; ListNode() : val(0), next(NULL) {} ListNode(int x) : val(x), next(NULL) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; class Solution { //填写该部分代码 public: ListNode* sortList(ListNode* head) { if(head==NULL||head->next==NULL) return head; ListNode *fast=head,*slow=head,*slow_pre=head; while(fast&&fast->next){ //利用快慢指针找到中间结点 slow_pre=slow; slow=slow->next; fast=fast->next->next; } slow_pre->next=NULL; //递归找到每一个子链表的中间结点 ListNode *l=sortList(head); ListNode *r=sortList(slow); //归并排序 return mergesort(l,r); } ListNode *mergesort(ListNode *l,ListNode *r){ //对链表进行排序 ListNode *head=new ListNode; ListNode *p=head; int a,b; while(l||r){ //归并排序，当链表为奇数时，必有一个子链表为空，此时赋值为无穷大，再进行比较 a=(l==NULL)?INT_MAX:l->val; b=(r==NULL)?INT_MAX:r->val; if(a<=b){ p->next=l; l=l->next; p=p->next; } else{ p->next=r; r=r->next; p=p->next; } } return head->next; } }; ListNode *createByTail() { ListNode *head; ListNode *p1,*p2; int n=0,num; int len; cin>>len; head=NULL; while(n<len && cin>>num) { p1=new ListNode(num); n=n+1; if(n==1) head=p1; else p2->next=p1; p2=p1; } return head; } void displayLink(ListNode *head) { ListNode *p; p=head; cout<<"head-->"; while(p!= NULL) { cout<<p->val<<"-->"; p=p->next; } cout<<"tail\n"; } int main() { ListNode* head = createByTail(); head=Solution().sortList(head); displayLink(head); return 0; }