AlgoPressAppearance
0148-排序链表
https://leetcode.cn/problems/sort-list
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 10^4] 内
-10^5 <= Node.val <= 10^5
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
思路：暴力冒泡排序（超时）
常规冒泡排序，主要是要注意交换节点
参考代码
csharp
public class Solution {
public ListNode SortList(ListNode head) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
//冒泡排序
ListNode p1 = head;
while(p1 != null){
ListNode p2 = p1.next;
while(p2 != null){
if(p1.val > p2.val){
int temp = p1.val;
p1.val = p2.val;
p2.val = temp;
}
p2 = p2.next;
}
p1 = p1.next;
}
return dummyHead.next;
}
}
思路2：归并排序
最适合链表的排序算法是归并排序
参考代码
- 将链表从中间分开，查找中点的方式是使用快慢指针，快的走两格，慢的走一格，快的走到底的时候慢的正好在中间
- 拆接出两个列表，递归调用排序(当最后只有一个节点的时候，会直接返回一个节点)
- 排序完成后，将两个链表合并
- 排序的时候，递归完成
csharp
public class Solution {
public ListNode SortList(ListNode head) {
if(head == null || head.next == null){
return head;
}
//找寻中点
ListNode fast = head;
ListNode slow = head;
while(fast != null){
fast = fast.next;
slow = slow.next;
if(fast != null){
fast = fast.next;
}
}
//slow 为中点
//构建第二个 List
ListNode list2 = slow;
//构建第一个 List
ListNode list1 = head;
ListNode cur = head;
while(cur != null){
if(cur.next == list2){
cur.next = null;
break;
}
cur = cur.next;
}
//递归调用
list1 = SortList(list1);
list2 = SortList(list2);
//Merge
ListNode result = MergeList(list1,list2);
return result;
}
//合并两个有序列表
private ListNode MergeList(ListNode head1, ListNode head2){
ListNode dummyHead = new ListNode();
ListNode cur = dummyHead;
while(head1 != null && head2 != null){
if(head1.val < head2.val){
cur.next = head1;
head1 = head1.next;
}
else{
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;
}
if(head1 != null){
cur.next = head1;
}
if(head2 != null){
cur.next = head2;
}
return dummyHead.next;
}
}