对没有明显访问节点的 LinkedList 进行排序？

Question

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

private LinkedList<T> list;

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

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

出于显而易见的原因，我们不允许使用集合或数组对其进行排序。我们只允许使用 Java LinkedList 和单个私有字段。

感谢您的任何意见。

编辑：如果可以的话，我宁愿避免使用 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;
}

Answer 2

没关系，您不需要任何私人访问权限。威胁列表只是列表 - 你有 get 和 set 方法。

但非常重要的是要考虑到随机访问链表的速度很慢！因此，您需要找到一种适用于彼此相邻的节点的排序。

在这种情况下，冒泡排序之类的方法实际上可能效果最好。
不是泡沫。 。名称不同，您需要进行 cmp 和交换相邻单元格。也许交换排序？