167 lines
3.9 KiB
JavaScript
167 lines
3.9 KiB
JavaScript
/**
|
||
* Definition for singly-linked list.
|
||
* function ListNode(val, next) {
|
||
* this.val = (val===undefined ? 0 : val)
|
||
* this.next = (next===undefined ? null : next)
|
||
* }
|
||
*/
|
||
|
||
function ListNode(val, next) {
|
||
this.val = (val === undefined ? 0 : val);
|
||
this.next = (next === undefined ? null : next);
|
||
}
|
||
|
||
/**
|
||
* @param {ListNode} head
|
||
* @return {ListNode}
|
||
*/
|
||
const sortList = function (head) {
|
||
|
||
};
|
||
|
||
/*
|
||
利用归并排序的思想，将链表分成两半，分别对两半进行排序，然后合并两个已排序的链表。
|
||
*/
|
||
function f1(head) {
|
||
if (!head || !head.next) return head;
|
||
let tail = head;
|
||
while (tail.next) {
|
||
tail = tail.next;
|
||
}
|
||
|
||
return merge(head, tail);
|
||
}
|
||
|
||
/*
|
||
将一个链表归并成一个有序列表，具体过程可以参考归并排序，不好描述，但不是很难
|
||
*/
|
||
function merge(head, tail) {
|
||
if (head === tail) return head;
|
||
|
||
// 快慢指针计算中间节点
|
||
let low = head;
|
||
let fast = head;
|
||
|
||
while (fast.next && fast.next.next) {
|
||
low = low.next;
|
||
fast = fast.next.next;
|
||
}
|
||
|
||
const mid = low;
|
||
// 将链表从中间截断
|
||
const head2 = mid.next;
|
||
mid.next = null;
|
||
|
||
// 将截断后的两个链表继续进行merge操作，之后将其合并成一个有序的链表返回
|
||
return mergeList(merge(head, mid), merge(head2, tail));
|
||
}
|
||
|
||
/*
|
||
合并两个有序链表
|
||
*/
|
||
function mergeList(l1, l2) {
|
||
// 至少一个为空的情况
|
||
if (!l1 || !l2) {
|
||
// 返回其中任意一个不为空的情况
|
||
return l1 || l2;
|
||
}
|
||
|
||
// 两个链表都不为空，将两个链表中的所有节点按大小拼接到dummy上，最后返回dummy.next
|
||
const dummy = new ListNode(0);
|
||
let cur = dummy;
|
||
while (l1 && l2) {
|
||
if (l1.val <= l2.val) {
|
||
cur.next = l1;
|
||
l1 = l1.next;
|
||
} else {
|
||
cur.next = l2;
|
||
l2 = l2.next;
|
||
}
|
||
cur = cur.next;
|
||
}
|
||
// 当一个链表处理完毕，还会右一个列表存在节点，将它拼接到cur.next上
|
||
cur.next = l1 === null ? l2 : l1;
|
||
return dummy.next;
|
||
}
|
||
|
||
/*
|
||
优化上面的写法，思路一致，但是只传入一个参数head，表示一个链表的头节点
|
||
*/
|
||
function f2(head) {
|
||
// 如果链表为空，或者只有一个节点，直接返回head
|
||
if (head === null || head.next === null) {
|
||
return head;
|
||
}
|
||
|
||
// 通过快慢指针寻找中间节点，将链表分成左右两部分
|
||
let slow = head;
|
||
let fast = head;
|
||
let prev = null;
|
||
while (fast && fast.next) {
|
||
prev = slow;
|
||
slow = slow.next;
|
||
fast = fast.next.next;
|
||
}
|
||
|
||
// 把链表从中间断开
|
||
prev.next = null;
|
||
|
||
const left = f2(head);
|
||
const right = f2(slow);
|
||
return mergeList(left, right);
|
||
}
|
||
|
||
/*
|
||
利用快速排序的思想，将链表分成三部分，left, pivot, right,left表示小于pivot的部分，right表示大于pivot的部分,最后将它们拼接起来。
|
||
*/
|
||
function quickSortList(head) {
|
||
if (!head || !head.next) return head;
|
||
|
||
const pivot = head;
|
||
const leftDummy = new ListNode(0);
|
||
const rightDummy = new ListNode(0);
|
||
let leftCur = leftDummy;
|
||
let rightCur = rightDummy;
|
||
let cur = head.next;
|
||
|
||
// 分组：< pivot 到 left，≥ pivot 到 right
|
||
while (cur) {
|
||
if (cur.val < pivot.val) {
|
||
leftCur.next = cur;
|
||
leftCur = leftCur.next;
|
||
} else {
|
||
rightCur.next = cur;
|
||
rightCur = rightCur.next;
|
||
}
|
||
cur = cur.next;
|
||
}
|
||
|
||
// 截断，避免串联成环
|
||
leftCur.next = null;
|
||
rightCur.next = null;
|
||
pivot.next = null; // 断开 pivot 和旧链表的联系
|
||
|
||
const leftSorted = quickSortList(leftDummy.next);
|
||
const rightSorted = quickSortList(rightDummy.next);
|
||
|
||
// 拼接三段：leftSorted + pivot + rightSorted
|
||
return concat(leftSorted, pivot, rightSorted);
|
||
}
|
||
|
||
// 拼接：将 left + pivot + right 接成一个链表并返回头结点
|
||
function concat(left, pivot, right) {
|
||
let head = pivot;
|
||
|
||
if (left) {
|
||
head = left;
|
||
let tail = left;
|
||
while (tail.next) {
|
||
tail = tail.next;
|
||
}
|
||
tail.next = pivot;
|
||
}
|
||
|
||
pivot.next = right;
|
||
return head;
|
||
}
|