ConstDefinition for singly-linked list. class ListNode { val: number next: ListNode | null constructor(val?: number, next?: ListNode | null) { this.val = (val===undefined ? 0 : val) this.next = (next===undefined ? null : next) } }
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function sortList(head: ListNode | null): ListNode | null {
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null) {
const dummy = new ListNode(-1, null);
let tail = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
}
else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = l1 || l2;
return dummy.next;
}
function middleNode(head: ListNode | null) {
let slow = head;
let fast = head;
let pre = head;
while (fast && fast.next) {
pre = slow;
slow = slow!.next;
fast = fast.next.next;
}
pre!.next = null;
return slow;
}
if (!head || !head.next) {
return head;
}
const mid = middleNode(head);
const l1 = sortList(head);
const l2 = sortList(mid);
return mergeTwoLists(l1, l2);
};
148.排序链表
给你链表的头节点
head，请将其按 升序 排列并返回 排序后的链表 。你必须在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 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