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

Question

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

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

但我不知道该怎么做。

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

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

Answer 1

以下是您的操作方法：

识别（子）列表的尾节点。也称其为枢轴节点。
遍历链表，当尾节点的值大于枢轴的值时，在当前尾节点之后移动一个节点。为了能够移动节点，您需要在遍历列表时在当前节点后面有一个引用。使移动的节点成为尾节点（现在枢轴节点不再是尾节点）。当遇到枢轴节点时停止本次迭代。
现在你有两个子列表。 Recur into那些重复上面的逻辑。

这是 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));

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

How to implement quick sort for singly linked list?

sorting

linked-list

quicksort

data-structures