Сортировка 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.

Очень важно учесть, что связанный список работает медленно при произвольном доступе!Поэтому вам нужно найти сортировку, которая работает с узлами, которые находятся рядом друг с другом.

Что-то вроде пузырьковой сортировки в этом случае может работать лучше всего.Не пузырь,Название было другим, вам нужно поменять местами ячейки соседей.Поменять сортировку что ли?