java - 在没有明显访问节点的情况下对 LinkedList 进行排序？

Question

大家好。我希望有人能对此有所了解。我有一个家庭作业问题，要求我对给定的 LinkedList 进行排序并返回排序后的列表，如下所示:

private LinkedList<T> list;

// constructor
public SortedLinkedList(LinkedList<T> in){
}      

现在，我已经理解了我认为的逻辑(我可以使用简单的合并排序)，但我看不到访问节点本身的方法。我想到的是快速排序的细微变化，即使用头部作为枢轴并将链表排序为两个较小的链表，重复然后合并......但我想知道我是否可以用其他方式做到这一点.但是，由于我们无法真正访问任何私有(private)节点，因此我没有任何好主意。

出于显而易见的原因，我们不允许使用 Collections 或 Arrays 对其进行排序。我们只允许使用 Java LinkedList 和单个私有(private)字段。

感谢任何输入。

编辑:如果可以的话，我宁愿避免使用 toArray。

Answer 1

由于不允许使用其他类，因此我建议您使用冒泡排序。它更容易，性能也不错。下面是如何使用它:

public SortedLinkedList(LinkedList<T> in) {
    bubbleSort(in);
}

private void bubbleSort(LinkedList<T> in) {
    // Convert the LinkedList into an array called arr. You should know how to do this..
    // This code assumes that your resulting array is of type int. For others, adjust
    // the code appropriately.

    for(int i = arr.length - 1; i > 0; i--) {
        for(int j = 0; j < i; j++) {
            if(arr[j] > arr[j + 1])
                swap(array, j, j+1);
        }
    }
}

private void swap(int[] array, int i, int j) {
    int temp = 0;

    temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}