148. 排序链表（单链表

• 用容器保存所有所有链表结点，然后对其做结构体排序，让所有结点在容器内按照权值升序排列
• 再正序遍历容器，修改前n-1个结点的后继为其容器内的后继结点；最后令最后一个结点的指针域为NULL；

• 划分：设立快慢双指针，当快指针遍历到链尾，慢指针正好到链中间位置；然后中间位置处断链，递归两个子链表的左结点
• 合并：合并两个有序的链表，为方便 *** 作设立伪头结点，不断比较并取出两个链表中数据域权值小的那个加入结果链中，最后两链表若有剩余直接跟在结果链后，返回我们所设立的伪头结点的后继即可

class Solution {
public:
	static bool cmp(ListNode* a,ListNode* b){
		return a->val<b->val;//按权值从小到大排序 
	}
    ListNode* sortList(ListNode* head) {
        if(head==NULL)return head;//判空 
		vector<ListNode*>v;//保存所有链表结点 
		ListNode* p=head;
		while(p!=NULL){
			v.push_back(p);
			p=p->next;
		} 
		sort(v.begin(),v.end(),cmp);
		for(int i=0;i<v.size()-1;i++){//对链表前n-1个结点修改后继 
			v[i]->next=v[i+1];
		} 
		v[v.size()-1]->next=NULL;//链尾指向NULL
		return v[0]; 
    }
};

class Solution {
public:       
    ListNode* sortInList(ListNode* head) {
        if(head==NULL||head->next==NULL)return head;
    	//划分
		ListNode *p=head->next,*q=head,*t;//设立快慢双指针，当快指针遍历到链尾时，慢指针正好到链中间位置 
		while(p!=NULL&&p->next!=NULL){//链长偶数时，用p!=NULL判空；链长奇数时，用p->next!=NULL判空 
			p=p->next->next;
			q=q->next;
		} 
		t=q->next; 
		q->next=NULL;//在链表中点处断链 
		ListNode *l=sortInList(head),*r=sortInList(t);//递归两个子链表的左结点 
		//合并 
		ListNode *list=new ListNode(0);p=list;//新建链表头结点，p指向新建链表头结点 
		while(l!=NULL&&r!=NULL){//合并两个有序的链表，结果链表链尾指针p链接上数据域小的链表，然后令该链表和结果链表链尾指针p均后移 
			if(l->val<r->val)p->next=l,l=l->next;
			else p->next=r,r=r->next;
			p=p->next;
		} 
		if(l!=NULL)p->next=l;//如果两链表还有剩余，则直接链接在结果链后即可 
		else p->next=r;
		return list->next;//返回伪头结点外的链表 
    }
};