如何实现单链表的快速排序

Question

我知道快速排序不能直接应用于单链表。

在快速排序中需要进行一些修改，使其与单链表兼容。

但我不知道该怎么做。

注意：-我不想用另一个节点交换一个节点的值。实际上，我想通过更改所需节点的下一个指针来对链表进行排序。

所以请详细说明如何做到这一点。

Answer 1

以下是如何做到这一点：

• 标识(子(列表的尾部节点。也称之为轴心节点
• 遍历列表，并在当前尾部节点的值大于轴的值时将节点移动到该节点之后。为了能够移动节点，您需要在遍历列表时在当前节点后面有一个引用。使移动的节点成为尾部节点(枢轴节点现在不再是尾部节点(。遇到轴心节点时停止此迭代
• 现在您有两个子列表。重复上述逻辑

以下是JavaScript中的一个实现：

class Node {
constructor(value, next=null) {
this.value = value;
this.next = next;
}
}
function quickSort(head, tail) {
if (tail == null || head == null || head == tail) return head;
let pivot = tail;
let curr = head;
let prev = null;
while (curr != pivot) {
let next = curr.next;
if (curr.value > pivot.value) {
// Move node after tail
if (prev == null) {
head = next;
} else {
prev.next = next;
}
curr.next = tail.next;
tail.next = curr;
tail = curr;
} else {
prev = curr;
}
curr = next;
}
// Sort right and left sublists with recursion
if (pivot != tail) pivot.next = quickSort(pivot.next, tail);
return quickSort(head, prev);
}
// Some helper/utility functions
function getTail(head) {
if (head == null) return null;
while (head.next != null) {
head = head.next;
}
return head;
}
function createList(arr) {
let head = null;
for (let i = arr.length - 1; i >= 0; i--) {
head = new Node(arr[i], head);
}
return head;
}
function toArray(head) {
let arr = [];
while (head != null) {
arr.push(head.value);
head = head.next;
}
return arr;
}
// Demo:
// Create list from array
let head = createList([4,2,6,1,5,3]);
// Apply quick sort
let tail = getTail(head);
head = quickSort(head, tail);
// Print
console.log(toArray(head));