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

Question

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

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

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

由于显而易见的原因，不允许使用Collections或Arrays对其进行排序。我们只允许使用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并交换相邻的单元格。也许是交换排序?