我实现了一个经典的双链接列表：

class Node<T> {
    protected T data;

    protected Node<T> next, prev;
}

class DoublyLinkedList<T extends Comparable<T>> {
    protected Node<T> front;
    protected Node<T> back;
    protected int size;

    // methods
}

现在为了能够排序，我添加了以下实现经典快速排序算法的方法：

public void sort(Comparator<T> comparator) {
    quickSort(front, back, comparator);
}

private void quickSort(Node<T> begin, Node<T> end, Comparator<T> comparator) {
    if (end != null && begin != end && begin != end.next) {
        var temp = partition(begin, end, comparator);
        quickSort(begin, temp.prev, comparator);
        quickSort(temp.next, end, comparator);
    }
}

private Node<T> partition(Node<T> begin, Node<T> end, Comparator<T> comparator) {
    var pivot = end.data;

    var i = begin.prev;
    Node<T> next;

    for (var j = begin; j != end; j = next) {
        next = j.next;
        if (comparator.compare(j.data, pivot) < 0) {
            i = (i == null) ? begin : i.next;

            swapData(i, j);
        }
    }

    i = (i == null) ? begin : i.next;
    swapData(i, end);

    return i;
}

private void swapData(Node<T> a, Node<T> b) {
    var temp = a.data;
    a.data = b.data;
    b.data = temp;
}

上面的代码产生了正确的结果，但是，我决定交换节点而不是数据，所以我介绍了以下方法：

private void swapNodes(Node<T> a, Node<T> b) {
    if (a == b) return;

    if (a == null || b == null) {
        throw new NullPointerException();
    }

    if (a.next == b) {
        var before = a.prev;
        var after = b.next;

        link(before, b);
        link(b, a);
        link(a, after);
    } else if (b.next == a) {
        var before = b.prev;
        var after = a.next;

        link(before, a);
        link(a, b);
        link(b, after);
    } else {
        var aPrev = a.prev;
        var aNext = a.next;
        var bPrev = b.prev;
        var bNext = b.next;

        link(aPrev, b);
        link(b, aNext);
        link(bPrev, a);
        link(a, bNext);
    }
}

private void link(Node<T> a, Node<T> b) {
    if (a != null)
        a.next = b;
    else
        front = b;
    if (b != null)
        b.prev = a;
    else
        back = a;
}

并将这些更改添加到 partition 方法：

private Node<T> partition(Node<T> begin, Node<T> end, Comparator<T> comparator) {
    var pivot = end.data;

    var i = begin.prev;
    Node<T> next;

    for (var j = begin; j != end; j = next) {
        next = j.next;
        if (comparator.compare(j.data, pivot) < 0) {
            i = (i == null) ? begin : i.next;

            //swapData(i, j);
            swapNodes(i, j);
            i = j;
        }
    }

    i = (i == null) ? begin : i.next;
    //swapData(i, end);
    swapNodes(i, end);

    //return i;
    return end;
}

在这一点上，代码工作不正常，我不知道为什么。我错过了什么？
编辑：
预期的输出是排序后的输入，而在第二种情况下则不是。
例子：

Initial :[2, 9, 8, 3, 6, 2, 4, 1, 7, 6]
Expected:[1, 2, 2, 3, 4, 6, 6, 7, 8, 9]
Actual:  [1, 3, 2, 4, 2, 6, 9, 6, 7, 8]

在这里可以找到一个工作示例：https://ideone.com/uqrzy1
编辑2：
提供了一个简短的示例和输入/输出。