题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
出处

思路

归并排序即可。

代码

class Solution {
public:ListNode*  merge(ListNode *h1,ListNode *h2) {ListNode *head = nullptr;if(h1->val<h2->val){head = h1;h1=h1->next;}else{head = h2;h2=h2->next;}ListNode *rear = head;while(h1&&h2){if(h1->val<h2->val){rear->next=h1;h1=h1->next;}else{rear->next=h2;h2=h2->next;}rear=rear->next;}if(h1)rear->next=h1;if(h2)rear->next=h2;return head;}void two_sort(ListNode * head){if(!head->next) return;int t=head->val;if(t>head->next->val){head->val=head->next->val;head->next->val=t;}}ListNode* sortList(ListNode* head) {if(!head||!head->next) return head;if(!head->next->next){two_sort(head);return head;}vector<ListNode*> lists;ListNode* p=head;ListNode* q=head;while(p){lists.push_back(p);q=p->next;if(q){p=q->next;q->next=nullptr;//断链}elsep=nullptr;}for(auto l:lists){two_sort(l);}int i=0,j=1;while(j<lists.size()){p=merge(lists[i],lists[j]);lists.push_back(p);i+=2;j+=2;}return p;}
};