代码语言：javascript复制
// 剑指 Offer II 077. 链表排序
/**
* @param {ListNode} head
* @return {ListNode}
*/
var sortList = function (head) {
// 1. 首先判断当前链表不存在 ，或链表只有一个节点，则直接返回 head
if (!head || !head.next) {
return head;
}
// 2. 获取分割的右侧链表
let rightLists = split(head);
// 3. 获取分割的左侧链表, 当获取到右侧链表后，会将链表断开，从而剩余 head 为 左侧链表
let leftLists = head;
// 4. 返回合并并排序后的链表
return mergeList(sortList(leftLists), sortList(rightLists));
};
// 排序并合并左右链表
function mergeList(leftLists, rightLists) {
// 创建一个空的链表
let res = new ListNode();
// 复制一份当前空的链表
let temp = res;
// 判断左侧链表存在，且左右链表也存在
while (leftLists !== null && rightLists !== null) {
// 如果左侧链表值小于右侧链表值
if (leftLists.val <= rightLists.val) {
// 将空链表的下一个节点指向值小的链
res.next = leftLists;
// 左侧链表指针向后移动一位，继续遍历
leftLists = leftLists.next;
} else if (leftLists.val > rightLists.val) {
// 否则当右侧链表节点值小，同理，将小值赋值给 res
res.next = rightLists;
// 右侧链表指针后移一位
rightLists = rightLists.next;
}
// 同时，每次循环，将新创建的链表的指针后移一位，为了连接下一个节点
res = res.next;
}
// 如果循环结束，左侧链表不为 null，说明左侧链表有剩余，拼接左侧链表
if (leftLists !== null) {
res.next = leftLists;
}
// 如果循环结束，右侧链表不为 null，说明右侧链表有剩余，拼接右侧链表
if (rightLists !== null) {
res.next = rightLists;
}
// 返回创建链表的 next，因为第一个节点没有值
return temp.next;
}
// 分割链表为左右链表
function split(head) {
// 使用快慢指针循环
let slow = head;
let fast = head.next;
// 当快指针指向最后一个节点时，慢指针刚好指向中间的节点
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
// 断开 head 指针下一个节点
let lists = slow.next;
slow.next = null;
// 返回慢指针指向的节点的下一个，即为分割后的右侧链表
return lists;
}参考链接
