题解 | #单链表的排序#
单链表的排序
https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08
暴力选择排序，时间复杂度O(n^2)，空间复杂度O(1)，目前还未超时
class Solution {
public:
ListNode* sortInList(ListNode* head) {
// write code here
if(!head || !head->next) return head;
ListNode *h=(ListNode*)malloc(sizeof(ListNode));
ListNode *res=(ListNode*)malloc(sizeof(ListNode));
h->next=head;
ListNode *p=h,*p1=h,*q=h->next,*q1=h->next,*r=res;
int min=INT_MAX;
while(q){
if(q->val<min){
p1=p;
q1=q;
min=q->val;
}
p=p->next;
q=q->next;
if(!q){
p1->next=q1->next;
r->next=q1;
r=r->next;
p1=h;
q1=h->next;
min=INT_MAX;
q=h->next;
p=h;
}
}
return res->next;
}
};