java排序没有明显访问节点的LinkedList？

Question

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

private LinkedList<T> list;

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

现在，我已经了解了我认为的逻辑（我可以使用一个简单的合并排序），但是我看不到访问节点本身的方法。我想到的是quicksort的一个微小变化，即使用头部作为轴心，将linkedlist排序为两个较小的，重复，然后合并。。。但是我想知道我是否可以用其他的方法。然而，由于我们不能真正访问任何私有节点，我没有什么好主意

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

谢谢你的意见

编辑：如果我能帮上忙，我宁愿避免使用toArray

Answer 1

没关系，你不需要任何私人访问。威胁列表就像威胁列表一样——你有获取和设置方法

<>非常重要的是考虑链表在随机访问中是慢的！因此，您需要找到一种排序，它可以处理彼此相邻的节点

在这种情况下，像“气泡排序”这样的方法可能是最有效的。 不是泡沫。名称不同，需要cmp和交换neigbourh单元格。也许吧

Answer 2

由于不允许使用其他类，我建议您使用冒泡排序。它更简单，性能也没那么差。以下是如何使用它：

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;
}