问题描述
LeetCode 148. 排序链表 (opens in a new tab)，难度中等。
给你链表的头结点 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 * 104]内 -105 <= Node.val <= 105
**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
题解
Solution.java
public ListNode sortList(ListNode head) {
if (head == null) return null;
ListNode prev = new ListNode(Integer.MIN_VALUE, head);
ListNode curr = prev.next;
while (curr != null) {
// 判断当前节点是否满足排序要求
if (curr.next != null && curr.val <= curr.next.val && curr.val >= prev.val) {
prev = prev.next;
curr = curr.next;
continue;
}
// 将 temp 从链表中隔离出来
ListNode temp = curr;
// prev curr 节点后移
prev.next = curr.next;
curr = curr.next;
// 如果当前节点是链首节点，则更新 head 节点
if (temp == head) {
head = prev.next;
}
// 将 temp.next 设置为 null
temp.next = null;
// temp 节点插入链表
ListNode sortedPrev = new ListNode(Integer.MIN_VALUE, head);
boolean flag = false; // 判断是否插入成功，未成功则插入链尾
while (sortedPrev.next != null) {
if (temp.val <= sortedPrev.next.val) {
// 如果当前节点插在链首，则更新 head 节点
if (sortedPrev.next == head) {
head = temp;
}
temp.next = sortedPrev.next;
sortedPrev.next = temp;
flag = true;
break;
}
sortedPrev = sortedPrev.next;
}
if (!flag) {
// 如果当前节点插在链首，则更新 head 节点
if (sortedPrev.next == head) {
head = temp;
}
sortedPrev.next = temp;
}
}
return head;
}