@[Echidna](/user/82284) 如果某些情况下有空间上的限制的话怕是不行，比如 $1TB$ 硬盘上存满了链表的信息，要求原地排列链表中的数据.（可能不符合事实，但是有总比没有好吧）
by Terrible @ 2022-05-14 22:22:22
@[Terrible](/user/195942) 什么神奇条件
by Echidna @ 2022-05-14 22:25:09
归并排序貌似可以？
递归然后每次传入两个首指针返回俩首指针。
返回的俩首指针保证连着的链有序然后合并。
找指针可以暴扫，反正单次合并也是O(n)的
by bh1234666 @ 2022-05-14 22:28:58
之前写大作业的时候写过一个单链表的快排
双向链表差不多思路应该也行
```cpp
void qsort(LinkList begin,LinkList end){
if(begin==end)return;
int key=begin->data;
LinkList p=begin,q=begin->next;
while(q!=end){
if(q->data<key){
p=p->next;
swap(p->data,q->data);
}
q=q->next;
}
swap(p->data,begin->data);
qsort(begin,p);
qsort(p->next,end);
return;
}
status SortList(LinkList L){
if(!L)return -1;
qsort(L->next,NULL);
return OK;
}
```
by windflower @ 2022-05-15 07:21:19